3 ms·

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

by 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.

by tgv 3y ago

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.