An Analytical Model of k-Ary n-Cube under Spatial Communication Locality

Author

Hu Kai ; Wang Zhe

Author_Institution

Sch. of Comput. Sci. & Eng., Beihang Univ., Beijing, China

fYear

2010

fDate

20-23 April 2010

Firstpage

24

Lastpage

29

Abstract

The method of spatial communication locality is adopted in many real parallel programs. But as we know, the definition of spatial communication locality is not consistent among existing analytical models and its impacts to latency and throughput have not been reported systematically. K-ary n-cube has been widely used in practical parallel computers, which supports communication locality well. In this paper, we use binary parameters - local message fraction and local domain´s radius to describe spatial locality. Then we give an analytical model of k-ary n-cube under spatial communication locality by M/G/1 queuing model, and the situation that a message´s length is less than the network radius in wormhole switching is considered. The results from simulation show close agreement with our analytical model.

Keywords

multiprocessor interconnection networks; parallel programming; queueing theory; M/G/1 queuing model; binary parameters; k-ary n-cube; local message fraction; network radius; parallel computers; parallel programs; spatial communication locality; spatial locality; wormhole switching; Analytical models; Communication switching; Computer networks; Concurrent computing; Delay; Multiprocessor interconnection networks; Queueing analysis; Telecommunication traffic; Throughput; Traffic control; M/G/1 queuing model; k-ary n-cube; spatial communication locality; virtual channel; wormhole;

fLanguage

English

Publisher

ieee

Conference_Titel

Advanced Information Networking and Applications Workshops (WAINA), 2010 IEEE 24th International Conference on

Conference_Location

Perth, WA

Print_ISBN

978-1-4244-6701-3

Type

conf

DOI

10.1109/WAINA.2010.30

Filename

5480922