Towards connectivity-guaranteed power-gating large-scale on-chip networks

In this work, we present an efficient and practical algorithm, named COPAL (Connectivity preserving algorithm), to identify routers, that will cause network disconnection in an off position, based on a distributed depth-first search (DFS) through 'neighbor-to-neighbor' communication. The algorithm allows the runtime system to make effective power-gating decisions in on-chip network based systems. For an N-node network, the time complexity of COPAL is O(N) and the total number of messages sent in classifying nodes' criticality in optimizing network connectivity is of the order of 2N_log2(N). FPGA implementation shows that the algorithm is scalable and the required hardware resource overhead is minimal.