http://citeseer.ist.psu.edu/trinder98algorithm.html
This is more of what I was getting at; although for massively parallel systems the actual examples are all off the mark.
So far I have examined two algorithms; bitonic sort and parallel prefix scan. I have some clarifications on the parallel prefix scan.
You can visualize the two parts of the parallel prefix scan starting with n threads, and at each stage decreasing the number of threads by n/2 till you have 1 thread. So the algorithms starts with an inverted pyramid of threads.
Second off, you run from 1 thread back to N threads; this is a normal pyramid assuming you picture time increasing down; each level has 2*n more threads active than the level before it.
So we are all used to the terms gather and scatter. The parallel prefix scan basically maps a certain type of gather operation followed by a specific scatter. I believe the descriptions given in the paper really are not very good; and in any case the algorithm isn't easy to visuals *even* if you attempt to visualize it in terms of gather and scatter. All gather and scatter do is provide the thread management in this case.
Next up is the bitonic sort. That is an algorithm that sorts somewhat efficiently (not that I know a better algorithm) in a massively parallel system. It has an interesting property in that it takes a fixed number of stages regardless of the condition of the input. This algorithm is somewhat difficult to visualize; and the description I see on the web are generally really bad. Luckily I bought a book on massively parallel systems a long time ago and it contains a really, really good description of the algorithm.
This contains some pretty darn cool visualizations of it working, however:
http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm
Anyway, if you visualize the algorithm correctly, which is exactly what a parallelization strategy is supposed to provide for you, then it isn't quite so darn tough to reason about the algorithms. Bitonic sort is very cool in that it basically builds up inversely sorted sequences (increasing/decreasing) called bitonic sequences from unordered data. Each stage takes in twice the number of elements as the stage before it, and it requires log(n) stage-groupings to work correctly.
It all comes down to algorithm visualization and then concise implementation. I believe that separating code from parallelization strategy helps in both respects, and the parallelization strategy should be reusable for different problems. Furthermore I believe that a system build to support the use of parallelization strategies could provide much more benefit in terms of debuggability, memory and speed profiling as well as optimizations than a system that was not built with such steps in mind.
For instance, lets say I want a parallel max/min operation. I would use the gather (begin with many threads; end with one) parallelization strategy along with some min,max operation. The compilation system could check that I am accessing the shared memory or scratch pad as efficiently as possible and could generate the code to run the operation efficiently taking into account the fact that you are using the gather pattern.
This is a trivial example, but I guarantee it wouldn't work the way you think it would upon first attempt on a CUDA processor. Unless you already implemented sum, because min/max are identical operations to sum, and would use the same gather pattern.
Chris
Saturday, July 26, 2008
Sunday, July 13, 2008
Ruminations on opengl
I have been rolling the idea of using thinking of rendering a particular item to the screen as executing all of the opengl state calls used for that item. All of them.
Meaning glEnable(GL_BLEND), as well as glDisable(GL_CULL_FACE) as well as glUniform and glUseProgram.
Given all the necessary state to render a given object, you have a large state vector. Now it wouldn't be efficient to actually program like this, but it makes sense, and sets the stage to think about things in an interesting way.
There are two concepts that I believe are important here:
First, given the set of objects you intend to render, I can produce a set of opengl state vectors assuming you need to set every single opengl state variable for every single item you want to render.
Now you would like to optimize this. Lets say you render a couple times and record, for each state item, if it was different from the last state item and if so, now many different items you found.
Now you sort each state vector by the number of different instances of each state property you found. Next you sort your entire render list by the state vectors. Now if you walk through the state vectors you are guaranteed to need to change the minimal number of gl state for each item in the state vector. You could add expense information to different operations in the sense that you some gl state properties are expensive to set (glUseProgram) and some aren't.
That gives you an extensible way to order your rendering operations on opengl objects where actually changing the state is slowing the program down.
Lets now take a look at exactly what a state vector is, or perhaps rather what it reminds me of.
The other place I have seen a large number of state items was a CSS system for html I wrote once. The result of a success full CSS system is a large vector of properties you apply to this html object during the rendering phase.
Perhaps there could be a graphics css system where the result is the opengl state vector you need to rendering this particular piece of geometry? I need to think about this for a while to see if it goes anywhere, but it is a start.
Chris
Meaning glEnable(GL_BLEND), as well as glDisable(GL_CULL_FACE) as well as glUniform and glUseProgram.
Given all the necessary state to render a given object, you have a large state vector. Now it wouldn't be efficient to actually program like this, but it makes sense, and sets the stage to think about things in an interesting way.
There are two concepts that I believe are important here:
First, given the set of objects you intend to render, I can produce a set of opengl state vectors assuming you need to set every single opengl state variable for every single item you want to render.
Now you would like to optimize this. Lets say you render a couple times and record, for each state item, if it was different from the last state item and if so, now many different items you found.
Now you sort each state vector by the number of different instances of each state property you found. Next you sort your entire render list by the state vectors. Now if you walk through the state vectors you are guaranteed to need to change the minimal number of gl state for each item in the state vector. You could add expense information to different operations in the sense that you some gl state properties are expensive to set (glUseProgram) and some aren't.
That gives you an extensible way to order your rendering operations on opengl objects where actually changing the state is slowing the program down.
Lets now take a look at exactly what a state vector is, or perhaps rather what it reminds me of.
The other place I have seen a large number of state items was a CSS system for html I wrote once. The result of a success full CSS system is a large vector of properties you apply to this html object during the rendering phase.
Perhaps there could be a graphics css system where the result is the opengl state vector you need to rendering this particular piece of geometry? I need to think about this for a while to see if it goes anywhere, but it is a start.
Chris
Some thoughts about concurrency
A while back, when I found out about F#'s syntax trees, I thought that perhaps you could use them to program CUDA programs; or in general massively parallel systems.
In addition, I just spoke with Jeff about high level languages and how they enable certain types of optimizations that lower level programs make excessively difficult to get right.
http://spiral.ece.cmu.edu:8080/pub-spiral/abstract.jsp?id=1
Finally, I have been trying to understand what Monads are and exactly what parser combinators are. I still don't really understand Monads, but I am not too far off. I think if I took a week and really messed around with Haskell, I could figure them out pretty well.
I spoke with one of the guys in charge of CUDA development about F# or rather functional languages and his exact quote was "How does this help c++ programmers trying to program in CUDA?"
I didn't have a great answer to this right off the bat, but I am in the nascent stages of having a pretty good answer.
Check out the parallel scan algorithm description for CUDA processors systems:
http://beowulf.lcs.mit.edu/18.337/lectslides/scan.pdf.
The important thing to notice is that there is a high level description of the algorithm, where basically the author talks about walking your way from the leaves of a binary tree to the root and back. Each node is actually a bit of code, and the level of the tree you are running at is the argument. The depth of the tree tells you how many threads are running at a given time (or whether each thread will do several computations in the case where there are more leaves than threads).
Parallel prefix scan uses a binary numeric operator (+) . This operator tends to be very easy to perform interesting parallelization with because it is commutative and associative; which allows you to use a distributive property in clever ways. I do not think this algorithm would work with (-), but I am not certain. Anyway, you have a bit of code that takes numeric arguments and that you can prove has various properties.
Then you can separate the operation itself from the application or algorithm context (the weird binary tree meta-algorithm). The algorithm context could be an instance of a set of parallel algorithm context, lets call this binary-apply. So in some ways, if you call (binary-apply + ), then you *could* automatically parallelize things.
Later in the prefix scan paper you get some interesting details about the local memory tricks you need to apply in order to make using a certain type of memory on the GPU efficient. These memory tricks could probably be automated, since all the answer involves is careful and clever application of an offset to the local memory index per given tree node read and write requests.
There are a couple things that would be interesting to take from this.
The first is that overall you probably have many different algorithm patterns you would like to apply: Matrix multiply is going to use one type of algorithm pattern, bitonic sort probably uses a very different one, and finally this parallel prefix scan exposes yet another algorithm pattern. So in essence, I am describing a set of parallel combinators, much like the parser combinators other authors have spoke at length about.
The second is that given a specific operation (result[n] = result[n-1] + input[n]), you *should* be able to figure out automatic parallelization of the operation, but it *has* to be described in certain terms. The should part makes me thing that for some problems (or most problems), this may be a pipe dream and may in fact be provably NP complete. But for those problems that you can do automatic parallelization, it would be nice if there was some system of doing this.
The third is that given something described using a given parallel combinator, you can debug it at a higher level, perhaps graphically, *before* you run it on 1000s of pieces of hardware. The language can ensure that reads and write *cannot* happen to the same local space at the same level of the tree. This level of debuggability of parallel algorithms is another holy grail.
Anyway, given the fact that I see three *very* different algorithm patterns and I can think of a high level description of those algorithm patterns, I believe there is room to say that some further exploration of the idea of parallel combinators makes a lot of sense.
Chris
In addition, I just spoke with Jeff about high level languages and how they enable certain types of optimizations that lower level programs make excessively difficult to get right.
http://spiral.ece.cmu.edu:8080/pub-spiral/abstract.jsp?id=1
Finally, I have been trying to understand what Monads are and exactly what parser combinators are. I still don't really understand Monads, but I am not too far off. I think if I took a week and really messed around with Haskell, I could figure them out pretty well.
I spoke with one of the guys in charge of CUDA development about F# or rather functional languages and his exact quote was "How does this help c++ programmers trying to program in CUDA?"
I didn't have a great answer to this right off the bat, but I am in the nascent stages of having a pretty good answer.
Check out the parallel scan algorithm description for CUDA processors systems:
http://beowulf.lcs.mit.edu/18.337/lectslides/scan.pdf.
The important thing to notice is that there is a high level description of the algorithm, where basically the author talks about walking your way from the leaves of a binary tree to the root and back. Each node is actually a bit of code, and the level of the tree you are running at is the argument. The depth of the tree tells you how many threads are running at a given time (or whether each thread will do several computations in the case where there are more leaves than threads).
Parallel prefix scan uses a binary numeric operator (+) . This operator tends to be very easy to perform interesting parallelization with because it is commutative and associative; which allows you to use a distributive property in clever ways. I do not think this algorithm would work with (-), but I am not certain. Anyway, you have a bit of code that takes numeric arguments and that you can prove has various properties.
Then you can separate the operation itself from the application or algorithm context (the weird binary tree meta-algorithm). The algorithm context could be an instance of a set of parallel algorithm context, lets call this binary-apply. So in some ways, if you call (binary-apply + ), then you *could* automatically parallelize things.
Later in the prefix scan paper you get some interesting details about the local memory tricks you need to apply in order to make using a certain type of memory on the GPU efficient. These memory tricks could probably be automated, since all the answer involves is careful and clever application of an offset to the local memory index per given tree node read and write requests.
There are a couple things that would be interesting to take from this.
The first is that overall you probably have many different algorithm patterns you would like to apply: Matrix multiply is going to use one type of algorithm pattern, bitonic sort probably uses a very different one, and finally this parallel prefix scan exposes yet another algorithm pattern. So in essence, I am describing a set of parallel combinators, much like the parser combinators other authors have spoke at length about.
The second is that given a specific operation (result[n] = result[n-1] + input[n]), you *should* be able to figure out automatic parallelization of the operation, but it *has* to be described in certain terms. The should part makes me thing that for some problems (or most problems), this may be a pipe dream and may in fact be provably NP complete. But for those problems that you can do automatic parallelization, it would be nice if there was some system of doing this.
The third is that given something described using a given parallel combinator, you can debug it at a higher level, perhaps graphically, *before* you run it on 1000s of pieces of hardware. The language can ensure that reads and write *cannot* happen to the same local space at the same level of the tree. This level of debuggability of parallel algorithms is another holy grail.
Anyway, given the fact that I see three *very* different algorithm patterns and I can think of a high level description of those algorithm patterns, I believe there is room to say that some further exploration of the idea of parallel combinators makes a lot of sense.
Chris
Sunday, May 25, 2008
Tuesday, April 22, 2008
Been a long time
I bit off more than I could easily chew at work recently.
Actually, I have been really working hard for about 3 weeks, with last week being the culmination and the hardest, and this week I am ramping down.
We haven't refactored the code base for so long, and I decided to do something to address a few outstanding technical issues with the product that ended up being a lot more work than I had originally accounted for.
This is the first time I have worked with a multiple document system. Add to that the fact that we keep the files in a datastructure that matches their structure in memory. There is no translation step on load or save. This means that links (urls) between files are just strings, they don't point at anything. If you change a document's location, or you move a resource, you had to run through the entire project looking for links to the renamed document or the moved resource to update them.
Needless to say, this didn't scale well.
Now, we parse urls into special objects that build a graph of the documents, the objects in the documents, and how they link to each other. We build a document graph. This sort of low level change, in a product as sophisticated as Blackfish, really takes a lot of work. It reduced complexity of move, rename, and delete operations considerably; but it increases the static complexity of the system. Anyway, it was hard, but it works and it is cool, clean, and fast.
I also had a bit of a breakdown physically two weeks ago. Sometimes I will train various different sports until I enter a state of physical exhaustion.
Real exhaustion isn't something that happens after you run a long time. You may be temporarily exhausted, but it takes weeks of overtraining to reach a true physical exhausted state. There are several key indicators you are overdoing it, but I don't usually notice them until they are pretty far along. High heart rate, even during the evening. Failure to sleep effectively, moodiness, pretty much all conditions I have without being exceptionally drained. You also stop healing effectively which is the largest problem.
Anyway, I pretty much took 2 weeks off from sports. Getting a very time consuming video game (Space Rangers 2) helped a lot. This game is pretty much all about zoning out wandering around the universe checking shizzle out. There is a point to it, but you can achieve it many different ways and there isn't a use to rushing. That and I am dancing with a very sweet girl from salsa so we just danced a lot (although I find it really tough to detach from hard work enough to dance well).
And, somewhat passive aggressively, I missed a meeting yesterday and just went to a baseball game. This pissed people off, but I needed the rest so what can I say? I got a somewhat direct email from the boss today telling me to either show up for the meeting or reschedule it. I don't intend to respond.
Anyway, I have started the physical stuff again, and what I am working on is wrapping up. The next 7 weeks should be OK for me. What I really need is some serious rest from this product, but I don't see that happening any time soon.
So, I am officially employed by NVIDIA. A large pay raise, and employee badge, and meeting some pretty cool people are what I have to show for it. Now I need to pay off the first loan on my house (the small one that ensures I don't have to pay loan insurance) and refinance the house. Rent it out and buy another.
Chris
Actually, I have been really working hard for about 3 weeks, with last week being the culmination and the hardest, and this week I am ramping down.
We haven't refactored the code base for so long, and I decided to do something to address a few outstanding technical issues with the product that ended up being a lot more work than I had originally accounted for.
This is the first time I have worked with a multiple document system. Add to that the fact that we keep the files in a datastructure that matches their structure in memory. There is no translation step on load or save. This means that links (urls) between files are just strings, they don't point at anything. If you change a document's location, or you move a resource, you had to run through the entire project looking for links to the renamed document or the moved resource to update them.
Needless to say, this didn't scale well.
Now, we parse urls into special objects that build a graph of the documents, the objects in the documents, and how they link to each other. We build a document graph. This sort of low level change, in a product as sophisticated as Blackfish, really takes a lot of work. It reduced complexity of move, rename, and delete operations considerably; but it increases the static complexity of the system. Anyway, it was hard, but it works and it is cool, clean, and fast.
I also had a bit of a breakdown physically two weeks ago. Sometimes I will train various different sports until I enter a state of physical exhaustion.
Real exhaustion isn't something that happens after you run a long time. You may be temporarily exhausted, but it takes weeks of overtraining to reach a true physical exhausted state. There are several key indicators you are overdoing it, but I don't usually notice them until they are pretty far along. High heart rate, even during the evening. Failure to sleep effectively, moodiness, pretty much all conditions I have without being exceptionally drained. You also stop healing effectively which is the largest problem.
Anyway, I pretty much took 2 weeks off from sports. Getting a very time consuming video game (Space Rangers 2) helped a lot. This game is pretty much all about zoning out wandering around the universe checking shizzle out. There is a point to it, but you can achieve it many different ways and there isn't a use to rushing. That and I am dancing with a very sweet girl from salsa so we just danced a lot (although I find it really tough to detach from hard work enough to dance well).
And, somewhat passive aggressively, I missed a meeting yesterday and just went to a baseball game. This pissed people off, but I needed the rest so what can I say? I got a somewhat direct email from the boss today telling me to either show up for the meeting or reschedule it. I don't intend to respond.
Anyway, I have started the physical stuff again, and what I am working on is wrapping up. The next 7 weeks should be OK for me. What I really need is some serious rest from this product, but I don't see that happening any time soon.
So, I am officially employed by NVIDIA. A large pay raise, and employee badge, and meeting some pretty cool people are what I have to show for it. Now I need to pay off the first loan on my house (the small one that ensures I don't have to pay loan insurance) and refinance the house. Rent it out and buy another.
Chris
Tuesday, April 1, 2008
F#
This language is a whole other world.
I bought a book on it (expert F#), and I will shortly buy another book on it (Foundations of F#).
After LISP, I didn't know if I could ever really be with another language, really. You see, I saw so much promise and possibilities in LISP.
The look of the code was amazing. The smooth and perfectly elegant lines of code, mixed with the intricate and somewhat arcane lines of meta-code. It still gives me chills to just think about it.
The infinite possibilities of a programmable programming language. Who wouldn't fall in love with LISP? Surely, I cannot blame myself for such fantasy.
Over time, our relationship soured. I yanked and urged common lisp to move into somewhat common territory (with a name like that, you would think it would be easy...). I kept thinking that I could somehow change it, to make the infinite possibilities I saw with it really happen.
The final straw was moving it to the .net platform. This is a necessary move, it would have been good for both of us. The next step.
There comes a point in every relationship where you must either move forward or move away. And as of late, I must admit that my thoughts have been absent and my intentions toward another have grown stronger.
I didn't even know who that other was.
Then one glorious day when I felt the need to express some of the joy that life had brought me, I caught the look of something I had seen from afar but never considered.
F# and I are curiously staring at each other over coffee at the moment. It appears that we really don't speak the same language; although when push comes to gentle, rhythmic shoving I am sure we will figure it out. We are so very viscerally attracted to each other that maybe we just have to get over our differences one way or another.
This will be a sweet and gentle love affair at first. I need to give myself time to adjust to new concepts, to the gloriously dirty feel of doing something very familiar with a very unfamiliar body.
Perhaps F# can help teach my wounded heart to love again...
Chris
I bought a book on it (expert F#), and I will shortly buy another book on it (Foundations of F#).
After LISP, I didn't know if I could ever really be with another language, really. You see, I saw so much promise and possibilities in LISP.
The look of the code was amazing. The smooth and perfectly elegant lines of code, mixed with the intricate and somewhat arcane lines of meta-code. It still gives me chills to just think about it.
The infinite possibilities of a programmable programming language. Who wouldn't fall in love with LISP? Surely, I cannot blame myself for such fantasy.
Over time, our relationship soured. I yanked and urged common lisp to move into somewhat common territory (with a name like that, you would think it would be easy...). I kept thinking that I could somehow change it, to make the infinite possibilities I saw with it really happen.
The final straw was moving it to the .net platform. This is a necessary move, it would have been good for both of us. The next step.
There comes a point in every relationship where you must either move forward or move away. And as of late, I must admit that my thoughts have been absent and my intentions toward another have grown stronger.
I didn't even know who that other was.
Then one glorious day when I felt the need to express some of the joy that life had brought me, I caught the look of something I had seen from afar but never considered.
F# and I are curiously staring at each other over coffee at the moment. It appears that we really don't speak the same language; although when push comes to gentle, rhythmic shoving I am sure we will figure it out. We are so very viscerally attracted to each other that maybe we just have to get over our differences one way or another.
This will be a sweet and gentle love affair at first. I need to give myself time to adjust to new concepts, to the gloriously dirty feel of doing something very familiar with a very unfamiliar body.
Perhaps F# can help teach my wounded heart to love again...
Chris
Saturday, March 29, 2008
That was fucking sweet
Had a blast last evening.
Too hung over to talk much about it.
Managed to get two awesome people to hook up with each other.
Have to work today and I am way too tired to do it so I will need to nap, but I am satisfied with the day already.
Chris
Too hung over to talk much about it.
Managed to get two awesome people to hook up with each other.
Have to work today and I am way too tired to do it so I will need to nap, but I am satisfied with the day already.
Chris
Subscribe to:
Posts (Atom)