# US 2012/0254879 A1 · Hierarchical task mapping

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254879 A1
- Document ID: US20120254879A1
- Status: Published application
- Kind: A1
- Application number: 13/413,286
- Filed: 2012-03-06
- Published: 2012-10-04
- Earliest claimed: 2011-03-31
- Assignees: International Business Machines Corporation
- Inventors: I-Hsin Chung; David J. Klepacki; Che-Rung Lee; Hui-Fang Wen
- Web page: https://patentgrep.com/patent/US20120254879A1

## CPC

- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

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

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The method 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.

### Claim 3 (depends on 2)

The method of claim 2, wherein the tasks that communicated with one another a predetermined number of times are partitioned into same group.

### Claim 4 (depends on 1)

The method 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.

### Claim 5 (depends on 1)

The method of claim 1, wherein the mapping can be performed based on Moore's space filling curve technique.

### Claim 6 (depends on 1)

The method of claim 1, wherein the fine tuning includes swapping assignment of tasks to physical processors within said each of the groups.

### Claim 7 (depends on 6)

The method 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.

### Claim 8 (depends on 7)

The method of claim 7, wherein communication cost of mapping including summation of communication time over all pairs of tasks is used to determine swapping.

### Claim 9 (depends on 8)

The method of claim 8, wherein said communication cost is determined based on runtime measurements of the tasks.

### Claim 10

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.

### Claim 11 (depends on 10)

The computer readable storage medium of claim 10, 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.

### Claim 12 (depends on 11)

The computer readable storage medium of claim 11, wherein the tasks that communicated with one another a predetermined number of times are partitioned into same group.

### Claim 13 (depends on 10)

The computer readable storage medium 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.

### Claim 14 (depends on 10)

The computer readable storage medium of claim 10, wherein the mapping can be performed based on Moore's space filling curve technique.

### Claim 15 (depends on 10)

The computer readable storage medium of claim 10, wherein the fine tuning includes swapping assignment of tasks to physical processors within said each of the groups.

### Claim 16 (depends on 15)

The computer readable storage medium of claim 15, 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.

### Claim 17 (depends on 16)

The computer readable storage medium of claim 16, wherein communication cost of mapping including summation of communication time over all pairs of tasks is used to determine swapping.

### Claim 18 (depends on 17)

The computer readable storage medium of claim 17, wherein said communication cost is determined based on runtime measurements of the tasks.

### Claim 19

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.

### Claim 20 (depends on 19)

The system of claim 19, 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.

### Claim 21 (depends on 19)

The system of claim 19, 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.

### Claim 22 (depends on 19)

The system of claim 19, wherein the fine tuning includes swapping assignment of tasks to physical processors within said each of the groups.

### Claim 23 (depends on 22)

The system of claim 22, wherein communication cost of mapping including summation of communication time over all pairs of tasks is used to determine swapping.

### Claim 24 (depends on 23)

The system of claim 23, wherein said communication cost is determined based on runtime measurements of the tasks.
