New approach to register communication in multi-core systems

The recent shift in the industry towards chip multiprocessor (CMP) makes it necessary that multi-threaded applications be mainstream computing. Most of the parallelization opportunities require looking for parallelism in local regions of code. To extract these parallelisms, especially for sequential applications, global multi-threaded instruction scheduling has been proposed. These techniques simultaneously extracted instructions from sequential codes and distributed them to cores. A key advantage ofthese global instruction scheduling techniques is the Multi-Threaded Code Generation (MTCG) algorithm which produce threads codes for each partition of graph and inserts communication and synchronization instructions to satisfy all inter-thread dependences. In this paper, we present an algorithm to reduce the communication and synchronization instructions. This algorithm based on thread aware dataflow analyses and adjacent list, models and optimizes register dependences among threads. The running time of the best algorithms, like Min-cut algorithm, is O (n3). But proposed algorithm act like Min-cut algorithm to reduce and insert communication instructions with running time of O (n2).

Keywords:

multi-core systems , multi-thread system , algorithm