Worst case performance analysis of the two dimensional binary buddy system^∗

^∗This research is supported in part by the Texas Advanced Research Program under grant no. 1028-ARP.

Abstract

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 2 ⁿ × 2 ⁿ . It is shown that for any unrestricted saturating sequence S, we have NETREQ(S)≧4^[n/2] + 4^{[n/2] − 1}+2^[n/2]+l and NETALLOC(S)≧4^[n/2] + 4^[n/2]; for any allocation-only saturating sequence S, we have NETALLOC(S)≧4 ⁿ + 1 and NETREQ(S)≧4 ⁿ⁻¹ + 2 ⁿ + 2.

Keywords:

• Partitionable mesh connected system
• performance evaluation
• two dimensional binary buddy system

^∗This research is supported in part by the Texas Advanced Research Program under grant no. 1028-ARP.

^∗This research is supported in part by the Texas Advanced Research Program under grant no. 1028-ARP.

Notes

^∗This research is supported in part by the Texas Advanced Research Program under grant no. 1028-ARP.