Fast and Efficient Processor Allocation Algorithm for Torus-based Chip Multiprocessors

Authors

Dawid Maksymilian Zydek, University of Nevada, Las VegasFollow
Henry Selvaraj, University of Nevada, Las VegasFollow

Document Type

Article

Publication Date

1-2011

Publication Title

Computers & Electrical Engineering

Volume

37

Issue

1

First page number:

91

Last page number:

105

Abstract

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.

Keywords

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

Disciplines

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

Language

English

Permissions

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

Repository Citation

Zydek, D. M., Selvaraj, H. (2011). Fast and Efficient Processor Allocation Algorithm for Torus-based Chip Multiprocessors. Computers & Electrical Engineering, 37(1), 91-105.