Bounded-collision memory-mapping schemes for data structures with applications to parallel memories

被引：7

作者：

Cordasco, Gennaro ^{[1
]}

Scarano, Vittorio

Rosenberg, Arnold L.

机构：

[1] Univ Salerno, Dipartimento Informat & Applicazioni RM Capocelli, I-84084 Fisciano, SA, Italy

[2] Univ Massachusetts, Dept Comp Sci, Amherst, MA 01003 USA

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 2007年 / 18卷 / 07期

基金：

美国国家科学基金会;

关键词：

parallel memory systems; data structures for parallel systems; bounded-conflict parallel memory access; data mapping; parallel architectures; parallel systems; data structures; graph labeling;

D O I：

10.1109/TPDS.2007.1024

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Techniques are developed for mapping structured data to an ensemble of parallel memory modules in a way that limits the number of conflicts, i.e., simultaneous accesses by distinct processors to the same memory module. The techniques determine, for any given conflict tolerance c, the smallest ensemble that allows one to store any n-node data structure "of type X" in such a way that no more than c nodes of a structure are stored on the same module. This goal is achieved by determining the smallest c-perfect universal graphs for data structures "of type X." Such a graph is the smallest graph that contains a homomorphic image of each n-node structure "of type X," with each node of the image holding <= c nodes of the structure. In the current paper,"type X" refers to rooted binary trees and three array-like structures: chaotic arrays, ragged arrays, and rectangular arrays. For each of these families of data structures, the number of memory modules needed to achieve conflict tolerance c is determined to within constant factors.

引用

页码：973 / 982

页数：10

共 29 条

[1] Multiple templates access of trees in parallel memory systems [J].

Auletta, V ;

De Vivo, M ;

Scarano, V .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1998, 49 (01) :22-39

[2] Toward a universal mapping algorithm for accessing trees in parallel memory systems [J].

Auletta, V ;

Das, SK ;

De Vivo, A ;

Pinotti, MC ;

Scarano, V .

FIRST MERGED INTERNATIONAL PARALLEL PROCESSING SYMPOSIUM & SYMPOSIUM ON PARALLEL AND DISTRIBUTED PROCESSING, 1998, :447-454

[3]

AULETTA V, 2002, IEEE T PAR DISTR SYS, V13

[4]

Bhatt S. N., 1989, SIAM J. Discrete Math, V2, P145

[5] ORGANIZATION AND USE OF PARALLEL MEMORIES [J].

BUDNIK, P ;

KUCK, DJ .

IEEE TRANSACTIONS ON COMPUTERS, 1971, C 20 (12) :1566-&

[6] PERFECT STORAGE REPRESENTATIONS FOR FAMILIES OF DATA-STRUCTURES [J].

CHUNG, FRK ;

ROSENBERG, AL ;

SNYDER, L .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (04) :548-565

[7]

CHUNG FRK, 1983, P LOND MATH SOC, V27, P203

[8] CONFLICT-FREE ACCESS TO PARALLEL MEMORIES [J].

COLBOURN, CJ ;

HEINRICH, K .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1992, 14 (02) :193-200

[9]

CORDASCO G, 2003, P INT C PAR DISTR CO

[10]

CORDASCO G, 2003, P 5 WORKSH DISTR DAT

← 1 2 3 →