Introduction
I am wondering if there is a generalization of parallel processing / asynchronous communication that explains/models how to deal with a hierarchy of parallel processes. Mainly looking for a reference of some sort, or an explanation if possible!
Basically I'm having the problem of how to handle the following situation. Say you have an application that handles user input, connects to a bunch of services (database, the "cloud" or other network APIs, etc.), does graphics processing, etc. You can consider parts of this thing running "in parallel". Assume we are in a purely abstract domain, and don't have a GPU chip and whatnot.
- The graphics component can process a bunch of vectors all at one time (abstracted away in GPU traditionally).
- We can make a bunch of network requests at the same time (abstracted away because we have physical servers all online at the same time).
- We can divide-and-conquer to resolve complex join queries (process data at the same time, no related abstraction I can think of).
- We can have a simulation of parallel processes in memory (like updating game entities "all at once", or updating all cells in a cellular automata all at once), even though they might be on a sequentially evaluated computer.
- Within the game entities, maybe their "body parts" all update "at the same time", simulating how our real bodies update in parallel so to speak.
- etc.
Given that we have multiple different parallel processing types in our application, the question is how to effectively evaluate them. I have no idea at this point, it is confusing.
Demonstrating My Confusion
One way I have tried looking at it is like this: The program is a global single process. Nested within that is a graphics processor, a query processor, a network processor, an entity processor, etc. Nested within the entity processor is a component processor.
- program processor: updates program
- graphics processor: updates vectors all at once
- query processor: updates data all at once
- network processor: makes requests all at once
- entity processor: updates entities all at once
- component processor: updates entity components all at once
Then I start getting confused. How to make it so all of these "at once" things can actually happen at once. One way would be to model them hierarchically. This diagram shows how that might work on a sequential computer (the bars represent time):
update entity | ------------------------------------- |
update component | ----- |
update component | --------- |
update component | --- |
update component | ------- |
update component | - |
And how it might look on a parallel computer:
update entity | --------- |
update component | ----- |
update component | --------- |
update component | --- |
update component | ------- |
update component | - |
But one problem here is, if an entity takes "too long", it perhaps shouldn't "block" the other entities from updating. So perhaps there is a time bound:
update entity | --------- | --------- | --------- |
update component | --------------- | | --------------- |
update component | --------- | --------- | --------- |
update component | --- | | --- | | --- |
update component | ------- | | ------- | | ------- |
update component | - | | - | | - |But that doesn't quite make sense, maybe it should be simply that every component is its own independent processor (so we remove the entity processor), so it updates every time that it can:
update component | --------------- | --------------- |
update component | --------- | --------- | --------- |
update component | --- | --- | --- | --- | --- | --- |
update component | ------- | ------- | ------- | ...
update component | - | - | - | - | - | - | - | - | - |This seems to mean that we can't have a hierarchy, and instead must make the parallel processors at the lowest level. I don't know but this seems similar to how reality works, but I can't tell if there are in reality "hierarchical processors". I haven't found an example of one.
Anyways, then we can have our whole program running in parallel, where query, component, network, and graphics are all independent of each other:
update query | ------- | ---- | ---------- | ------ | ...
update query | ---- | -- | - | -------- | -------- | ...
update query | ---------- | ------ | -- | ---------- | ...
...
update component | ...
update component | ...
update component | ...
...
update network | ...
update network | ...
update network | ...
...
update graphics | ...
update graphics | ...
update graphics | ...
...
But still, we may want to nest some parallel stuff within the query. Say we have, for each query processor, a "data" processor that does a quick comparison on a data field. Then we would have another hierarchical process:
update query | -------------------------- | ---------------- | ...
update data | -- | - | ---- | - | - | -- | - | - | --- | -- |
update data | --- | -- | -- | -- | ----- | -- | - | --- | - |
update data | ...
update data | ...
...
So it's confusing to see how you can run query in parallel, while at the same time running data in parallel underneath. I haven't seen any research on this topic.
Another part of the confusion / lack of understanding is about the network parallel processes. In reality, each network process (like an HTTP request) performs a whole slew of operations, and so could have its own tree of parallel processes. So then we have a large hierarchy of parallel processes:
program:
network:
1
1
1
2
1
1
1
2
1
2
1
3
2
1
1
2
2
3
1
network:
...
graphics:
...
query:
...
...
By this point I am having a hard time imagining how the parallelism could work. This makes me want to fall back to a simple array of processing elements approach, where there is just a grid of processing elements all doing a simple task, like the GPU.
■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■
| | | | | | | | | |
■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■
| | | | | | | | | |
■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■
| | | | | | | | | |
■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■
| | | | | | | | | |
■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■
| | | | | | | | | |
■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■
| | | | | | | | | |
■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■
| | | | | | | | | |
■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■
| | | | | | | | | |
■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■
| | | | | | | | | |
■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■ -- ■
But that gets me confused about how to apply it to the problem I described above (of having multiple types of parallel processes).
Finally, there is the confusion around how to simulate this on a sequential computer. To do this (using the component as an example), you could update each component until completion, sequentially. This means that you update each entity to completion, sequentially. Which seems to mean you update each program processor type to completion, sequentially (so entity, then query, then network, etc.). But that's not what you want. That would lead to basic sequential computation.
It's as if what you want is to perform one "step" in each at a time. But I don't see how you can perform one step in each at a time if they are hierarchical. That goes back to why not just go to the lowest level and create a simple processor array/grid.
Question
That leads me to the main question. If there is any research on this subject. On parallel processing where you have multiple types of processes, some of them seemingly hierarchical. Or if no research, how you would conceptualize of the situation. I can't tell if it's even possible to have a "hierarchical parallel processing machine". A generalization of that would be to somehow model a graph of parallel processing machines. That seems even more complicated.
The goal would be to simulate such parallel processing on a sequential computer. So:
- updating all the program processor types at once, which requires
- updating all game entities at once, which requires
- updating all components of an entity at once
- updating all queries at once, which requires
- updating all data fields at once
- updating all network requests at once
- ...
- ...
- updating all game entities at once, which requires
