Hierarchical task mapping

Abstract

Mapping tasks to physical processors in parallel computing system may include partitioning tasks in the parallel computing system into groups of tasks, the tasks being grouped according to their communication characteristics (e.g., pattern and frequency); mapping, by a processor, the groups of tasks to groups of physical processors, respectively; and fine tuning, by the processor, the mapping within each of the groups.

1 . A computer readable storage medium storing a program of instructions executable by a machine to perform a method of mapping tasks to physical processors in parallel computing system, comprising:
 partitioning tasks in the parallel computing system into groups of tasks, the tasks being grouped according to their communication pattern and frequency;   mapping, by a processor, the groups of tasks to groups of physical processors, respectively; and   fine tuning, by the processor, the mapping of tasks to processors within each of the groups.   
     
     
         2 . The computer readable storage medium of  claim 1 , wherein the partitioning is performed by utilizing a run-time communication matrix collected during run-time of the tasks, based on message passing interface communications occurring among the tasks, wherein the partitioning preserves locality of communication among the tasks. 
     
     
         3 . The computer readable storage medium of  claim 2 , wherein the tasks that communicated with one another a predetermined number of times are partitioned into same group. 
     
     
         4 . The computer readable storage medium of  claim 1 , wherein the tasks in each of the groups are classified into boundary tasks and interior tasks, wherein the boundary tasks are selected to maintain continuity of communication among said groups of tasks, and wherein the interior tasks can be swapped in fine tuning the mapping of tasks to processors within each of the groups. 
     
     
         5 . The computer readable storage medium of  claim 1 , wherein the mapping can be performed based on Moore's space filling curve technique. 
     
     
         6 . The computer readable storage medium of  claim 1 , wherein the fine tuning includes swapping assignment of tasks to physical processors within said each of the groups. 
     
     
         7 . The computer readable storage medium of  claim 6 , wherein the swapping is performed based on a local search method, wherein the tasks are classified into boundary tasks and interior tasks, the boundary tasks selected to maintain continuity and the interior tasks are swapped based on a greedy algorithm. 
     
     
         8 . The computer readable storage medium of  claim 7 , wherein communication cost of mapping including summation of communication time over all pairs of tasks is used to determine swapping. 
     
     
         9 . The computer readable storage medium of  claim 8 , wherein said communication cost is determined based on runtime measurements of the tasks. 
     
     
         10 . A system for mapping tasks to physical processors in parallel computing system, comprising:
 a processor;   a module operable to execute on the processor, and further operable to partition tasks in the parallel computing system into groups of tasks, the tasks being grouped according to their communication pattern and frequency, the module further operable to map the groups of tasks to groups of physical processors, respectively, the module further operable to fine tune the mapping of tasks to processors within each of the groups.   
     
     
         11 . The system of  claim 10 , wherein the module partitions the tasks by utilizing a run-time communication matrix collected during run-time of the tasks, based on message passing interface communications occurring among the tasks, wherein the partitioning preserves locality of communication among the tasks. 
     
     
         12 . The system of  claim 10 , wherein the tasks in each of the groups are classified into boundary tasks and interior tasks, wherein the boundary tasks are selected to maintain continuity of communication among said groups of tasks, and wherein the interior tasks can be swapped in fine tuning the mapping of tasks to processors within each of the groups. 
     
     
         13 . The system of  claim 10 , wherein the fine tuning includes swapping assignment of tasks to physical processors within said each of the groups. 
     
     
         14 . The system of  claim 13 , wherein communication cost of mapping including summation of communication time over all pairs of tasks is used to determine swapping. 
     
     
         15 . The system of  claim 14 , wherein said communication cost is determined based on runtime measurements of the tasks.