|
Code partitioning is the problem of dividing sections of code among a set
of processors for execution in parallel taking into account the
communication overhead between the processors. Code partitioning of large
amounts of code onto numerous processors requires variations to the
classical partitioning algorithms, in part due to the memory and time
requirements to partition a large set of data, but also due to the nature
of the target machine and multiple constraints imposed by its architectural
features.
In this paper, we present our experience in the design of enhancements to
the classical multi-level k-way partitioning algorithm to deal with large
graphs of over 1 million nodes, 5 constraints, and nodes of irregular size.
Our algorithm was implemented to produce code for a massively parallel
machine of up to 40,000 processors, and forms part of a hardware
description language compiler. The algorithm and the compiler were tested
on RTL designs for a next generation SPARC® processor. We present
performance results and comparisons for partitioning multi-processor
hardware designs.
|
