Fast and efficient processor allocation algorithm for torus-based chip multiprocessors

Document Type



Processor Allocator (PA) is a crucial factor in modern Chip MultiProcessors (CMPs). A modern CMP uses Network on Chip (NoC) as communication technique between cores. Thus, the topology of the implemented NoC has also significant impact on the CMP’s performance. A good processor allocation technique needs to be fast and ensure the highest possible system utilization. In this paper, we propose a processor allocation technique for such an efficient and fast PA. The PA is driven by a Bit Map Allocation for Torus (BMAT) algorithm, which is a technique designed for k-ary 2-cube topology. The proposed BMAT scheme is presented and described along with a new Busy List Allocation for Torus (BLAT), Sorting Allocation for Torus (SAT) and Stack Based Allocation for Torus (SBAT) algorithms. The presented techniques are compared with previously known important schemes for k-ary 2-mesh topology. The research ideas have been verified using experiments that have also been described in the paper. The presented simulation results reveal that the proposed processor allocation algorithm for k-ary 2-cube, as a technique for PA, achieves better allocation time than all other existing algorithms while the CMP with such a PA is characterized by very high system utilization.


Algorithms--Data processing; Computer architecture; Networks on a chip; Parallel computers; Parallel scheduling (Computer scheduling)


Computer and Systems Architecture | Computer Engineering | Controls and Control Theory | Digital Communications and Networking | Electrical and Computer Engineering | Hardware Systems | Systems and Communications


Use Find in Your Library, contact the author, or use interlibrary loan to garner a copy of the article. Publisher copyright policy allows author to archive post-print (author’s final manuscript). When post-print is available or publisher policy changes, the article will be deposited

UNLV article access

Search your library