TE task architecture
/*****************************************************************************/
Execution List
Concept:
Execution list is a realisation of a streaming processing of data. The concept
is to divide the data and its operations to a small chunks of code. Each chunk
is somehow dependant on other chunks. The thread of execution takes a first
chunk that can be processed and returns its result. This should unlock other
chunks which now can be processed. The execution is not deterministic - you
cannot tell when a given chunk will be executed.
What is so cool about it?
It scales very well as a number of execution units. If you have a 4 cpu
computer then the program should run abour 4 times faster then on a single
without any modifications, have 8 cpus, 8 times faster*
*this is actually less, due to certain protocol overhead.
To show you an example:
Consider a simple arythmetical expression
a + b * c + d / f * (g + h +j) * i + c - d - e
this can be expressed as:
((a + (b * c)) + ( ( ((d * i) * g) + ((d * i) * h) + ((d * i) * j) ) / f ) + ((c - d) - e))
this forms a graph of execution:
res = result of operation
Code: Select all
| col1 | col2 | col3 | col4 | col5 |
step 1: | (b * c) | (d * i) | (c - d) |
step 2: | (a+res) | (res*g) | (res*h) | (res*j) | (res-e) |
step 3: | | (res + res) | | |
step 4: | | (res + res) | |
step 5: | | (res/f) | |
step 6: | (res + res) | |
step 7: | (res + res)
step 8: | res
as you can see to count the expression 13 operations need to be performed
Each step shows operations which can be performed in parallel. 1 CPU will
need 13 ops.
How many ops for 2 cpus:
Code: Select all
step1: (b * c) and (d * i) unlock 4 ops - outstanding ops: 5
step2: (a+res) and (c + d) unlock 1 op - outstanding ops: 4
step3: (res*g) and (res*h) unlock 1 op - outstanding ops: 3
step4: (res*j) and (res-e) unlock 0 ops - outstanding ops: 1
step5: (res+res) unlocks 1 op - outstanding ops: 1
step6: (res+res) unlocks 1 op - outstanding ops: 1
step7: (res/f) unlocks 1 op - outstanding ops: 1
step8: (res+res) unlocks 1 op - outstanding ops: 1
step9: (res+res) unlocks 1 op - outstanding ops: 1
step10: result
so - adding 1 cpu increased speed by 30%.
The list of ops is
(b*c) | (d*i) | (c-d) | (a+res) | (res*g) | (res*h) | (res*j) |
(res-e) | (res+res) | (res+res) | (res/f) | (res+res) | (res+res)
OK - that does not seem too hot, 30% is a bit low. However, the main point is here
no need to recompile to add more processing power. 5 cpus will process this in 8 steps.
OK - still, not too hot.
To get the most of this it is best to consider the type of task you are making, this
scheme works best in:
Games operating on huge game object base (strategies ferinstance)
Rendering and ray tracing
Generally, where there is a huge base of objects that require
some action
Other I haven thought of
-------------------------------------------------------------------------------
Terms:
EXECUTOR:
Executor is the entity which traverses the container of tasks and performs them
one at a time
EXECUTION CONTAINER Exco
Exco is the entity which holds all tasks and contains logic needed to dispatch,
organize, add and remove tasks
EXECUTION CONTAINER ITERATOR Exco::iterator
Execution container iterator is an entity which, if properely created, always
points to a viable task in the Exco
TASK
Task is a single operation that can be invoked by an iterator
Use:
EXECUTOR traverses EXCO with the use of EXCO::iterator and does TASK until
all TASKS are completed
-------------------------------------------------------------------------------
IMPLEMENTATION NOTES:
EXCO uses std::list
There are 3 types of tasks
blocking_task - a task that will gather up to x executors and fire one controlled
task by one of them
single_task - a task that will allow 1 executor to activate it
multi_task - a task that will allow mutliple executors to activate it
-------------------------------------------------------------------------------
Usage:
1.Create your execution list.
ec::exco ex(numOfUsers);
num of users is amount of executors that will traverse a list. Note! It has to
be correct - otherwise all block tasks inside your exco will block indefinetly!
2. define your task
class my_task : public ec::single_task
{
my_task(exco& list) : single_task(list){};
~my_task(){};
void logic() // logic of your task, since this is a single task, then only
// one executor will enter here
{
std::cout << "my_task";
}
};
3. instantiate your task
for (int x = 0;x < 10;++x)
{
ex.insert(my_task(ex));
}
4. instantiate executor
std::vector<executor> execs;
for (int x = 0;x < numOfUsers;++x)
{
execs.push_back(executor(ex,"my_executor"));
}
5. Unless your app exits earlier, you should see 10 times the "my_task"
printed on the screen
--------------------------------------------------------------------------------
classes:
ec::exco - main execution list
ec::single_task - single task
ec::multi_task - multiple task
ec::block_task - blocking task
ec::executor - excutor which will create a thread
ec::thredlessExecutor - executor which will not create a thread