Connectivity-Sensitive Algorithm for Task Placement on a Many-Core Considering Faulty Regions

Future many-core chips are envisioned to feature up to a thousand cores on a chip. With an increasing number of cores on a chip the problem of distributing load gets more prevalent. Even if a piece of software is designed to exploit parallelism it is not an easy to place parallel tasks on the cores to achieve maximum performance. This paper proposes the connectivity-sensitive algorithm for static task-placement onto a 2D mesh of interconnected cores. The decreased feature sizes of future VLSI chips will increase the number of permanent and transient faults. To accommodate partially faulty hardware the algorithm is designed to allow placement on irregular core structures, in particular, meshes with faulty nodes and links. The quality of the placement is measured by comparing the results to two baseline algorithms in terms of communication efficiency.