Thursday, July 19, 2007
The intricate art in iteration space
I am looking at the very artsy figures in the "More iteration space tiling" paper by Michael Wolfe. I think I will write a few thoughts on the various figures in the paper when I complete reading that paper. Keep up the good work, y'all.
Thursday, June 7, 2007
Exercise work for "Programming Haskell" ppt files.
The expressive power of the Haskell foldr function is unbelievable!
1: The filter R (x:xs) function applies an equivalence relation R on every element in the list argument, (x:xs). If R evaluates true, the element x is appended to the result list otherwise it is dropped.
Example:
Main> filter (< 3) [1,2,3,4,5]
[1,2]
Relation function:
In the above filter application, (< 3) is the equivalence relation, R. One of the arguments in R is already specified as the value 3. It could be any expression that evaluate to the same type as the elementes of the list. Another condition is that when the function R acts on the elements in the result the result must be a boolean value.
The type signature of the relation R function is R :: (a -> Bool)
Haskell has a corny name called section to denote usually infix operations that is written in a prefix style. Sections are infix operations that are enclosed within a parenthesis. In the above example, (< 3) is a section. (< 3) x in prefix form is the same as x < 3 .
Moving on, the type signature of filter is type signature of R and the type signature of the remaining semantics. The remaining semantics is that filter takes a list parameter and generates another list parameter i.e. ([a] -> [b])
You can also say all of this in another way, the function filter takes 2 arguments, first one is a function with a signature (a -> Bool) and the second is a list of a generic type, called [a] and computes a result which is of a list of the same type as [a].
Concisely,
filter :: (a -> Bool) -> [a] -> [a]
2: The foldr f v (x:xs) function replaces the empty list constructor [] in (x:xs) with the function argument v, and the cons operator or (:) with f.
foldr can be concisely (and recursively) represented as
foldr f v (x:xs) = f x (foldr f v (x:xs))
One can construct a filter function using foldr as follows:
filt p (x:xs) = foldr (if p then x:xs else xs) [] (x:xs)
This means, for a given list, replace the empty list construct [] with [], if x is such that p x is true, replace list with (x:xs), else if p x is false, replace (x:xs) with xs.
Please correct me if I am wrong!
I found some pretty interesting list theory theorems in this page
http://hol.sourceforge.net/kananaskis-4-helpdocs/help/src/htmlsigs/rich_listTheory.html
HOL is an interesting link, but I got no idea yet on the use for this kind of tool or the reach for these algorithms.
Anyway! Adios. Hope you enjoyed reading this stuff as much as I am enjoying reading about this from the PPTs here:
http://www.cs.nott.ac.uk/~gmh/book.html
(Ram)
1: The filter R (x:xs) function applies an equivalence relation R on every element in the list argument, (x:xs). If R evaluates true, the element x is appended to the result list otherwise it is dropped.
Example:
Main> filter (< 3) [1,2,3,4,5]
[1,2]
Relation function:
In the above filter application, (< 3) is the equivalence relation, R. One of the arguments in R is already specified as the value 3. It could be any expression that evaluate to the same type as the elementes of the list. Another condition is that when the function R acts on the elements in the result the result must be a boolean value.
The type signature of the relation R function is R :: (a -> Bool)
Haskell has a corny name called section to denote usually infix operations that is written in a prefix style. Sections are infix operations that are enclosed within a parenthesis. In the above example, (< 3) is a section. (< 3) x in prefix form is the same as x < 3 .
Moving on, the type signature of filter is type signature of R and the type signature of the remaining semantics. The remaining semantics is that filter takes a list parameter and generates another list parameter i.e. ([a] -> [b])
You can also say all of this in another way, the function filter takes 2 arguments, first one is a function with a signature (a -> Bool) and the second is a list of a generic type, called [a] and computes a result which is of a list of the same type as [a].
Concisely,
filter :: (a -> Bool) -> [a] -> [a]
2: The foldr f v (x:xs) function replaces the empty list constructor [] in (x:xs) with the function argument v, and the cons operator or (:) with f.
foldr can be concisely (and recursively) represented as
foldr f v (x:xs) = f x (foldr f v (x:xs))
One can construct a filter function using foldr as follows:
filt p (x:xs) = foldr (if p then x:xs else xs) [] (x:xs)
This means, for a given list, replace the empty list construct [] with [], if x is such that p x is true, replace list with (x:xs), else if p x is false, replace (x:xs) with xs.
Please correct me if I am wrong!
I found some pretty interesting list theory theorems in this page
http://hol.sourceforge.net/kananaskis-4-helpdocs/help/src/htmlsigs/rich_listTheory.html
HOL is an interesting link, but I got no idea yet on the use for this kind of tool or the reach for these algorithms.
Anyway! Adios. Hope you enjoyed reading this stuff as much as I am enjoying reading about this from the PPTs here:
http://www.cs.nott.ac.uk/~gmh/book.html
(Ram)
Sunday, May 27, 2007
Some have given us 50 years or so for things to last as we know them. What next, Planet of the Apes?? Back to stone age?? This short sighted world does not quite feel like home at all, i.e. days when I used to imagine how everything circled around compassion.
Coming to computer architecture, one the one hand you have David Patterson delivering a lecture in PARC forum on how it is going to be grand many core era and the inevitable slow death of things we hold near and dear, Pentium IV, AMD Opteron, Power4, Itanium, and not to miss the unscalable yester years' misguiding notions like Alpha EV8 or 21464, notions @ http://www.cs.washington.edu/research/smt/. On the other hand you have venture capitalists claiming that the investments in Silicon are pointless. They are looking to sponsor projects only in Web 2.0! Unfortunately the next big thing will be Web 2.0, it seems. This Web 2.0 is all hype, right. Most of the smart audio projects seem to be circling around ipods. As one who does not possess ipod, I find this rather pointless. Secondly all this cool apps like, google word/excel etc web apps do not hold water. And they are not like a technical marvel. There is DocBook and likewise XML driven apps. So a tree structure intermediate language i.e. XML is primarily the basis for everything? But thinking positively does it mean revival of great stuff like Latex, which people never really adapted in a broad scale? Does not make much of a difference to me, especially and to some others I know. I have used Latex for a while and it has been my tool of choice to write a technical document.
Of late I am taking interest in data flow exectution machines. I am working on the compiler for a processor which has no register files or a common store as we know them. i.e it does not have a notion of a stack for parameter passing. What the is the computation model you may ask. Values do not stay at a place for more than a clock tick or two. Generated data must be either consumed or passed around to be used later. Complications arise especially if you try to compile to this from an imperative language like C, which is what they (including me) are trying to do here over the years... but there is just so much to do.
I am exploring if Dr. Kesav Pingali's work: "Dependency flow graphs: An algebraic approach to Program Dependencies" apply here. More on it later!
Coming to computer architecture, one the one hand you have David Patterson delivering a lecture in PARC forum on how it is going to be grand many core era and the inevitable slow death of things we hold near and dear, Pentium IV, AMD Opteron, Power4, Itanium, and not to miss the unscalable yester years' misguiding notions like Alpha EV8 or 21464, notions @ http://www.cs.washington.edu/research/smt/. On the other hand you have venture capitalists claiming that the investments in Silicon are pointless. They are looking to sponsor projects only in Web 2.0! Unfortunately the next big thing will be Web 2.0, it seems. This Web 2.0 is all hype, right. Most of the smart audio projects seem to be circling around ipods. As one who does not possess ipod, I find this rather pointless. Secondly all this cool apps like, google word/excel etc web apps do not hold water. And they are not like a technical marvel. There is DocBook and likewise XML driven apps. So a tree structure intermediate language i.e. XML is primarily the basis for everything? But thinking positively does it mean revival of great stuff like Latex, which people never really adapted in a broad scale? Does not make much of a difference to me, especially and to some others I know. I have used Latex for a while and it has been my tool of choice to write a technical document.
Of late I am taking interest in data flow exectution machines. I am working on the compiler for a processor which has no register files or a common store as we know them. i.e it does not have a notion of a stack for parameter passing. What the is the computation model you may ask. Values do not stay at a place for more than a clock tick or two. Generated data must be either consumed or passed around to be used later. Complications arise especially if you try to compile to this from an imperative language like C, which is what they (including me) are trying to do here over the years... but there is just so much to do.
I am exploring if Dr. Kesav Pingali's work: "Dependency flow graphs: An algebraic approach to Program Dependencies" apply here. More on it later!
Friday, March 2, 2007
Welcome to the wacky world of computer architecture
hiya!
Welcome to my blog on computer architecture!
A catchy phrase I came up with:
Computer architecture, where people take sides! (I believe found this phrase first, I will trademark this soon)
I have taken up the humble (humbling?) task of pointing out the idiosyncrasies that goes around in computer architecture circles. I sometimes set out to write about real stuff, including how a compiler pass works in one of the open source compilers, this or that and sometimes I would decide to screw around with some peer reviewed conference and journal papers.
Wacky computer architecture news will soon follow. For now, I will sign off with something less wacky, the warner cartoon, the sublime "porky in wackyland", the one and only at: http://www.youtube.com/watch?v=arNNWKYkc3I
Ramanar
Welcome to my blog on computer architecture!
A catchy phrase I came up with:
Computer architecture, where people take sides! (I believe found this phrase first, I will trademark this soon)
I have taken up the humble (humbling?) task of pointing out the idiosyncrasies that goes around in computer architecture circles. I sometimes set out to write about real stuff, including how a compiler pass works in one of the open source compilers, this or that and sometimes I would decide to screw around with some peer reviewed conference and journal papers.
Wacky computer architecture news will soon follow. For now, I will sign off with something less wacky, the warner cartoon, the sublime "porky in wackyland", the one and only at: http://www.youtube.com/watch?v=arNNWKYkc3I
Ramanar
Subscribe to:
Posts (Atom)