WORST CASE PERFORMANCE ANALYSIS OF THE 2-DIMENSIONAL BINARY BUDDY SYSTEM

被引：1
作者：
LI, KQ
CHENG, KH
机构：
[1] Department of Computer Science, University of Houston, Houston
来源：
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 1991年 / 38卷 / 3-4期
关键词：
PARTITIONABLE MESH CONNECTED SYSTEM; PERFORMANCE EVALUATION; 2 DIMENSIONAL BINARY BUDDY SYSTEM;
D O I：
10.1080/00207169108803964
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The worst case performance of the two dimensional binary buddy system is investigated. Tight lower bounds are given for two system performance measures, namely, NETREQ and NETALLOC, Let the system size be 2n × 2n. It is shown that for any unrestricted saturating sequence S, we have NETREQ(S)≧4[n/2] +4[n/2]-1+2[n/2] +1 and NETALLOC(S)≧4[n/2] +4[n/2]; for any allocation-only saturating sequence S, we have NETALLOC(S) ≧4n+l and NETREQ(S) ≧4n-1 + 2n+ 2. © 1991 Gordon and Breach Science Publishers S.A.
引用
收藏
页码：123 / 132
页数：10
相关论文
共 5 条
[1]   WORST CASE PERFORMANCE OF WEIGHTED BUDDY SYSTEMS [J].
CHOWDHURY, SK ;
SRIMANI, PK .
ACTA INFORMATICA, 1987, 24 (05) :555-564
[2]   A FAST STORAGE ALLOCATOR [J].
KNOWLTON, KC .
COMMUNICATIONS OF THE ACM, 1965, 8 (10) :623-&
[3]  
LI K, 1989, 1 ANN IEEE S PAR DIS, P358
[4]  
LI K, 1990, 18TH P ACM COMP SCI, P22
[5]   ON THE WORST CASE PERFORMANCE OF BUDDY SYSTEMS [J].
LLOYD, EL ;
LOUI, MC .
ACTA INFORMATICA, 1985, 22 (04) :451-473
1