5 ms·

This is really good. Thank you for this blog post. Asynchronous code, coroutines, async/await, parallelising problems is my deep interest and I blog about it e

This is really good. Thank you for this blog post. Asynchronous code, coroutines, async/await, parallelising problems is my deep interest and I blog about it everyday. I think the easiest way to parallelise is to shard your data per thread and treat your multithreaded (or multimachine) architecture as a tree - not a graph - where dataflow doesn't need to pass between tree branches. This is similar to the Rust's "no interior mutabiliy" and Rust data structures pattern. My machine can lock and unlock 61570760 times a second. But it can count to 2 billion in 1 second. So locks are expensive. I recently worked at parallelising the A* graph search algorithm that I'm using for code generation/program synthesis. For 16 processes it takes 35 seconds to synthesise a program but with 3 processes it takes 21 seconds. I think my approach to parallelising A* needs a redesign. We hit Amdahl's law when it comes to parallelising. I need to split up my problem into spaces that don't require synchronization/serialisation. EDIT: I've mentioned this whitepaper before ("Scalability! But at what COST?") but this whitepaper would be useful reading of anybody working on multithreaded or distributed systems. In summary: single threaded programs can easily be faster and more performant (wall clock time) than multithreaded/multimachine distributed machines, but they don't scale. https://www.usenix.org/system/files/conference/hotos15/hotos15-paper-mcsherry.pdf https://www.usenix.org/system/files/conference/hotos15/hotos...

tgv 3y ago
The basic algorithm of A* is very sequential, isn't it? It works by taking the best scoring unexpanded node and expand that. Most of the time, there's only one such node. When expansion has finished, you need to re-sort the queue/heap of unexpanded nodes. All those steps are sequential. So I guess the only gain is when the node expansion can be done in parallel; expanding the top-N nodes probably is counterproductive for many problems. How much you gain then depends on the time expansion takes. The advantage of parallelism then depends on how much time one step "down" takes.
- asimpletune 3y ago
  This is correct, and Bellman-Ford, while naive compared to A*, actually parallelizes much better. That said, an optimized Bellman-Ford doesn't even resemble the original, naive version of the algorithm.
- samsquire 3y ago
  Yes, I think I can take advantage of my particular problem to parallelise, which I'm still trying to work out. My neighbour scanning is dynamic and my neighbours and all neighbours from a node is independent from that point forwards, it shall not visit the exact same node. In essence my problem is kind of a tree. I am trying to infer data flow between two states including hidden states such as functions calls. My dream is that I can provide a start state and end state and the computer writes itself based on type information and data flow analysis of values. Here's my input data - which is what memory is set to and what registers are set to. start_state = { "memory": [0, 0, 0, 0], "rax": 0, "rbx": 1, "rcx": 2, "rdx": 3, "rsp": -1, "rdi": -1, "rbp": -1 } end_state = { "memory": [3, 1, 2, -1], "rax": 3, "rbx": 2, "rcx": 1, "rdx": 0, "rsp": 6, "rdi": -1, "rbp": -1 } # these functions take in a value and return another value minus_1_to_four = Function("minus1", -1, 4) four_to_five = Function("fourtofive", 4, 5) five_to_six = Function("fivetosix", 5, 6) This synthesises the following program in 16 seconds (I improved the heuristic function). Function values input and output can be in any register, but in my example they are all in the same register. With 3 processes it synthesises in 0.6 seconds. [start, mov %rax, (%rdx), mov %rbx, (%rbx), mov %rcx, (%rcx), mov %rdx, (%rsp), mov %rax, %rbp, mov %rdx, %rax, mov %rbp, %rdx, mov %rcx, %rbp, mov %rbx, %rcx, mov %rbp, %rbx, call minus1(rsp=-1) -> rsp=4, mov $-1, %rbp, call fourtofive(rsp=4) -> rsp=5, call fivetosix(rsp=5) -> rsp=6]
- lelanthran 3y ago
  I wouldn't say sequential. Maybe at implementations are sequential and state based because games need to pause the process on a frame refresh. A* is naturally recursive [1] and so can be parallelized as you go further. [1] unless I'm mistaking some other algorithm for A*, each new recursive call of all the neighbours can be started on a different thread or node.
asimpletune 3y ago
This is in a nutshell the moral of the performance story. I took a graduate level class in performance computing that was basically all lab based. In the end what I learned, overwhelmingly, first hand, is that in the performance computing world, what wins is what exploits the hardware intelligently. Theoretical advancements matter too but usually only in so much as they can translate to hardware. Although, there are some special case where even a slight theoretical gain matters even more than how it translates to hardware, but they're limited. Anyways, to that end, everything becomes about dividing work in a way that parallelizes nicely, exploits cache well, reduces the need to share information between threads, etc... and this ultimately comes down to data structures. However, these aren't your normal, fundamental data structures. Instead each problem sort of has some kind of exotic, hypothetically ideal data structure, that is fine tuned to exploit the machine's resources to the max for just that problem. By the time you're done they rarely resemble anything intelligible, let alone wha the whiteboard version of the algorithm was. In that vein, there are a few general trends that appear over and over again. Trees vs graphs is definitely one of of those trends, although that's more of a general theme and not a literal rule.
- cgio 3y ago
  That sounds very interesting. Would you be able to reference any such exotic data structure and maybe the process of getting to defining it?
  - asimpletune 3y ago
    I don't know any of their names, or if they even have names. My TA for that class had, at the time, one of the world's fastest SSSP implementations, and our last class was basically just spending the whole lab time understanding his personal implementation. It was really in that moment that it clicked for me that the more you come to understanding a problem in CS the more your code morphs from something general into becoming one big, bespoke data structure. Almost his entire program was just one giant data structure. So, I don't think this kind of thing has a name, nor can I say I really even understood it, but I do remember he used a lot of bags. For reference, we spent the whole class doing SSSP on a graph representing every road in the United States. The naive A*/Dijkstra implementation took like 45 min, and naive bellman-ford never finished (probably days/weeks). By the end of the class I was so proud to have parallelized Bellman-Ford to the point where it took like 30s or something. And my TA's record breaking implementation was <1s. All of this was on a normal university linux desktop. It's kind of like programming = logic + data. However, there's a continuum between the two, and on the far, extreme end of that spectrum, the structured access of the data can be the program itself.
brutusborn 3y ago
Can you share any of the parallel A* code? I’m currently looking at using A* for use in generative design and am pretty ignorant about parallelising code. Would love to learn more!
- samsquire 3y ago
  I've taken a very naive approach and it does NOT scale. It uses python multiprocessing. I think the fScore updates pickling and serialization - communication and synchronization lock overhead is slowing it down. It simply does not parallelise. This is my code generator/program synthesiser, it synthesises assembly instructions from two given states of memory and registers to take it from one to the other, including hidden states such as functions. https://replit.com/@Chronological/SlidingPuzzle3#main.py https://replit.com/@Chronological/SlidingPuzzle3#main.py
  - brutusborn 3y ago
    Thanks, regardless of ability to parallelise it looks interesting.
    - samsquire 3y ago
      I've changed the algorithm to not send fScore updates and treat each branch as independent. This speeds it up from 16 seconds to 320 milliseconds. I am thinking how to make the algorithm scale, by creating better and alternative program candidates in each thread.
_hl_ 3y ago
FYI, there are lots of papers on parallel shortest path algorithms. If an approximate solution suffices, there’s also a lot of research available on that, often with some parameter that lets you trade more computation for a tighter approximation. It's not a problem that parallelises particularly well though, so not sure if you'll see good gains in practice. If you can restrict the structure of your graphs (e.g. planar) then some very efficient methods exist.
hinkley 3y ago
When I was noodling with the Traveling Salesman problem, I was sure that what I really needed was to spend X% of available resources on the Big Gamble (a low probability algorithm with fast results), Y% on a common heuristic and the rest on the honest work of plowing through the linear equations progressively culling the remaining scenarios that need to be tested. I had limited success with this though. I just haven’t done enough LP to make anything noteworthy, and it was a tool sharpening exercise, which made me a little more effective at more mundane batch processing tasks, not a great mind of NP-completeness.
OoooooooO 3y ago
Isn't a tree just a graph that is directed and acyclic (DAG)? So a tree is just a subtype of a graph?
- ironSkillet 3y ago
  A tree is a subtype of graph. However, a DAG is not a tree if it has cycles once you forget direction, meaning paths can join up again after splitting. This distinction matters because when different paths "join up" again, there is often complicated data duplication/integration that is necessary in order order to combine the results. On a distributed system, it may mean data passing over a network, which you want to avoid.
- Ruphin 3y ago
  A tree is a subtype of a graph, but it is not the same as a DAG. A diamond-shaped directed graph (edges A->B, A->C, B->D, C->D) is a DAG, but not a tree.
- pxc 3y ago
  In graph theory, trees are undirected. In computing, trees usually have two features that differentiate them from their more minimal graph theoretical cousins: they are (a) directed and (b) rooted (a particular vertex is designated as the root, and every vertex can be walked to from that vertex). But yeah. Some graphs are trees. And you can construct trees within graphs for efficiently navigating connected graphs, which is done in various important and famous algorithms.
magicalhippo 3y ago
> I need to split up my problem into spaces that don't require synchronization/serialisation. When I first got a dual CPU (before "cores" were a thing) computer, I decided I'd try dipping my feet in some "proper" parallel coding. I started with something simple, parallelizing a quicksort routine. This seemed quite trivial: instead of recursing, add the spans to be sorted to a list. I then spawned a thread per CPU, which fetched a span from the list, did a single quicksort pass on it and added up to two new spans to the list. Rinse repeat until list was empty. Since each span was non-overlapping, the threads only had to synchronize while accessing the list of tasks. When benchmarking it became clear that while there was a good performance win for large arrays, for short arrays the multithreaded code was much slower than the non-multithreaded version. At my hardware the threshold was around 50k items for integer elements and 20k or so for string elements, IIRC. I added a threshold detection, where the thread would do a regular recursive quicksort on the span if the length was below the threshold, and this yielded significantly better results. And with that the harsh reality of multithreading hit me: no free lunch. It was clear the threshold varies not just with element type (slow/complex comparators would reduce the threshold, and vice versa) but with the details of the hardware. So a hardcoded threshold was out of the picture, and it would have to be dynamically determined at runtime. Was a great learning experience though.
- magicalhippo 3y ago
  For those who might wonder why, the quicksort splits the array into half and then repeats on the two halves. Thus the majority of spans are small and quickly processed, and hence the naive multithreaded version leads to lock contention as the threads fight to access the shared list of spans.
jasfi 3y ago
I'd like your opinion: channels or locks? This is really for a program I'm writing in Nim, so perhaps it depends on how channels are implemented?
rkuska 3y ago
This is exactly a reason why I like Scylla as a database. One shard per CPU. Each shard owning different partition of data. Great performance.

tgv 3y ago

The basic algorithm of A* is very sequential, isn't it? It works by taking the best scoring unexpanded node and expand that. Most of the time, there's only one such node. When expansion has finished, you need to re-sort the queue/heap of unexpanded nodes. All those steps are sequential. So I guess the only gain is when the node expansion can be done in parallel; expanding the top-N nodes probably is counterproductive for many problems. How much you gain then depends on the time expansion takes. The advantage of parallelism then depends on how much time one step "down" takes.

asimpletune 3y ago
This is correct, and Bellman-Ford, while naive compared to A*, actually parallelizes much better. That said, an optimized Bellman-Ford doesn't even resemble the original, naive version of the algorithm.
samsquire 3y ago
Yes, I think I can take advantage of my particular problem to parallelise, which I'm still trying to work out. My neighbour scanning is dynamic and my neighbours and all neighbours from a node is independent from that point forwards, it shall not visit the exact same node. In essence my problem is kind of a tree. I am trying to infer data flow between two states including hidden states such as functions calls. My dream is that I can provide a start state and end state and the computer writes itself based on type information and data flow analysis of values. Here's my input data - which is what memory is set to and what registers are set to. start_state = { "memory": [0, 0, 0, 0], "rax": 0, "rbx": 1, "rcx": 2, "rdx": 3, "rsp": -1, "rdi": -1, "rbp": -1 } end_state = { "memory": [3, 1, 2, -1], "rax": 3, "rbx": 2, "rcx": 1, "rdx": 0, "rsp": 6, "rdi": -1, "rbp": -1 } # these functions take in a value and return another value minus_1_to_four = Function("minus1", -1, 4) four_to_five = Function("fourtofive", 4, 5) five_to_six = Function("fivetosix", 5, 6) This synthesises the following program in 16 seconds (I improved the heuristic function). Function values input and output can be in any register, but in my example they are all in the same register. With 3 processes it synthesises in 0.6 seconds. [start, mov %rax, (%rdx), mov %rbx, (%rbx), mov %rcx, (%rcx), mov %rdx, (%rsp), mov %rax, %rbp, mov %rdx, %rax, mov %rbp, %rdx, mov %rcx, %rbp, mov %rbx, %rcx, mov %rbp, %rbx, call minus1(rsp=-1) -> rsp=4, mov $-1, %rbp, call fourtofive(rsp=4) -> rsp=5, call fivetosix(rsp=5) -> rsp=6]
lelanthran 3y ago
I wouldn't say sequential. Maybe at implementations are sequential and state based because games need to pause the process on a frame refresh. A* is naturally recursive [1] and so can be parallelized as you go further. [1] unless I'm mistaking some other algorithm for A*, each new recursive call of all the neighbours can be started on a different thread or node.

asimpletune 3y ago

This is in a nutshell the moral of the performance story. I took a graduate level class in performance computing that was basically all lab based. In the end what I learned, overwhelmingly, first hand, is that in the performance computing world, what wins is what exploits the hardware intelligently. Theoretical advancements matter too but usually only in so much as they can translate to hardware. Although, there are some special case where even a slight theoretical gain matters even more than how it translates to hardware, but they're limited. Anyways, to that end, everything becomes about dividing work in a way that parallelizes nicely, exploits cache well, reduces the need to share information between threads, etc... and this ultimately comes down to data structures. However, these aren't your normal, fundamental data structures. Instead each problem sort of has some kind of exotic, hypothetically ideal data structure, that is fine tuned to exploit the machine's resources to the max for just that problem. By the time you're done they rarely resemble anything intelligible, let alone wha the whiteboard version of the algorithm was. In that vein, there are a few general trends that appear over and over again. Trees vs graphs is definitely one of of those trends, although that's more of a general theme and not a literal rule.

cgio 3y ago
That sounds very interesting. Would you be able to reference any such exotic data structure and maybe the process of getting to defining it?
- asimpletune 3y ago
  I don't know any of their names, or if they even have names. My TA for that class had, at the time, one of the world's fastest SSSP implementations, and our last class was basically just spending the whole lab time understanding his personal implementation. It was really in that moment that it clicked for me that the more you come to understanding a problem in CS the more your code morphs from something general into becoming one big, bespoke data structure. Almost his entire program was just one giant data structure. So, I don't think this kind of thing has a name, nor can I say I really even understood it, but I do remember he used a lot of bags. For reference, we spent the whole class doing SSSP on a graph representing every road in the United States. The naive A*/Dijkstra implementation took like 45 min, and naive bellman-ford never finished (probably days/weeks). By the end of the class I was so proud to have parallelized Bellman-Ford to the point where it took like 30s or something. And my TA's record breaking implementation was <1s. All of this was on a normal university linux desktop. It's kind of like programming = logic + data. However, there's a continuum between the two, and on the far, extreme end of that spectrum, the structured access of the data can be the program itself.

brutusborn 3y ago

Can you share any of the parallel A* code? I’m currently looking at using A* for use in generative design and am pretty ignorant about parallelising code. Would love to learn more!

samsquire 3y ago
I've taken a very naive approach and it does NOT scale. It uses python multiprocessing. I think the fScore updates pickling and serialization - communication and synchronization lock overhead is slowing it down. It simply does not parallelise. This is my code generator/program synthesiser, it synthesises assembly instructions from two given states of memory and registers to take it from one to the other, including hidden states such as functions. https://replit.com/@Chronological/SlidingPuzzle3#main.py https://replit.com/@Chronological/SlidingPuzzle3#main.py
- brutusborn 3y ago
  Thanks, regardless of ability to parallelise it looks interesting.
  - samsquire 3y ago
    I've changed the algorithm to not send fScore updates and treat each branch as independent. This speeds it up from 16 seconds to 320 milliseconds. I am thinking how to make the algorithm scale, by creating better and alternative program candidates in each thread.

_hl_ 3y ago

FYI, there are lots of papers on parallel shortest path algorithms. If an approximate solution suffices, there’s also a lot of research available on that, often with some parameter that lets you trade more computation for a tighter approximation. It's not a problem that parallelises particularly well though, so not sure if you'll see good gains in practice. If you can restrict the structure of your graphs (e.g. planar) then some very efficient methods exist.

hinkley 3y ago

When I was noodling with the Traveling Salesman problem, I was sure that what I really needed was to spend X% of available resources on the Big Gamble (a low probability algorithm with fast results), Y% on a common heuristic and the rest on the honest work of plowing through the linear equations progressively culling the remaining scenarios that need to be tested. I had limited success with this though. I just haven’t done enough LP to make anything noteworthy, and it was a tool sharpening exercise, which made me a little more effective at more mundane batch processing tasks, not a great mind of NP-completeness.

OoooooooO 3y ago

Isn't a tree just a graph that is directed and acyclic (DAG)? So a tree is just a subtype of a graph?

ironSkillet 3y ago
A tree is a subtype of graph. However, a DAG is not a tree if it has cycles once you forget direction, meaning paths can join up again after splitting. This distinction matters because when different paths "join up" again, there is often complicated data duplication/integration that is necessary in order order to combine the results. On a distributed system, it may mean data passing over a network, which you want to avoid.
Ruphin 3y ago
A tree is a subtype of a graph, but it is not the same as a DAG. A diamond-shaped directed graph (edges A->B, A->C, B->D, C->D) is a DAG, but not a tree.
pxc 3y ago
In graph theory, trees are undirected. In computing, trees usually have two features that differentiate them from their more minimal graph theoretical cousins: they are (a) directed and (b) rooted (a particular vertex is designated as the root, and every vertex can be walked to from that vertex). But yeah. Some graphs are trees. And you can construct trees within graphs for efficiently navigating connected graphs, which is done in various important and famous algorithms.

magicalhippo 3y ago

> I need to split up my problem into spaces that don't require synchronization/serialisation. When I first got a dual CPU (before "cores" were a thing) computer, I decided I'd try dipping my feet in some "proper" parallel coding. I started with something simple, parallelizing a quicksort routine. This seemed quite trivial: instead of recursing, add the spans to be sorted to a list. I then spawned a thread per CPU, which fetched a span from the list, did a single quicksort pass on it and added up to two new spans to the list. Rinse repeat until list was empty. Since each span was non-overlapping, the threads only had to synchronize while accessing the list of tasks. When benchmarking it became clear that while there was a good performance win for large arrays, for short arrays the multithreaded code was much slower than the non-multithreaded version. At my hardware the threshold was around 50k items for integer elements and 20k or so for string elements, IIRC. I added a threshold detection, where the thread would do a regular recursive quicksort on the span if the length was below the threshold, and this yielded significantly better results. And with that the harsh reality of multithreading hit me: no free lunch. It was clear the threshold varies not just with element type (slow/complex comparators would reduce the threshold, and vice versa) but with the details of the hardware. So a hardcoded threshold was out of the picture, and it would have to be dynamically determined at runtime. Was a great learning experience though.

magicalhippo 3y ago
For those who might wonder why, the quicksort splits the array into half and then repeats on the two halves. Thus the majority of spans are small and quickly processed, and hence the naive multithreaded version leads to lock contention as the threads fight to access the shared list of spans.

jasfi 3y ago

I'd like your opinion: channels or locks? This is really for a program I'm writing in Nim, so perhaps it depends on how channels are implemented?

rkuska 3y ago

This is exactly a reason why I like Scylla as a database. One shard per CPU. Each shard owning different partition of data. Great performance.