The project "resource theory for microprocessors" shows how the execution time depends on a number of parameters. It could be concluded as:
- each calculation is a node referring to othe calculations. A directed graf results. For this graf the calculations are placed in processors and the vertecies on the communication links.
- the latency time for a problem is approximately equal to the longest time for calculation from a leaf to the root.
- for a link the latency time corresponds to the time for commnication. Often the time for calculations are negligible.
- the order for the calculations has hardly no influence
The best allocation algorithm casuses the time for calculations from leaf to root be lower than a particular value for all branches and this particular value should be as low as possible.
The delay time for a link depends on the load of the link. Therefore the load should be distributed to the links.
Placement could generally speaking be considered as placing components and performing wiring on printed circuit boards. This problem does not have a best solution because the problem is NP-complete. However thera are good solutions.
The problem above is for one set of input data so that there is only one graph with a particular content. At other inputs the graph is changed. In certain cases as in signal processing the graph has the same structure but different contents. In a compilation problem the graph has a quite different structure and contents.
The allocation algorithm must be design such that alternative placements for the changed graphs also results in short latency time.
Probably a random based placement of subgraphs is proper.
Placement could be performed at load time or run time. In order to control the latter one, there must be a cost function.
- It is probable that those meters used for input to the cost function have a lot of noise. The question is how such noise influences the allocation.
- When the allocation is performed run time, the performance is measured on already executed parts of a graph. How does this influence the performance of the allocation for future executions?
Different allocation algorithms are studied, primarily those based on simulated annealing.