Institution: Stanford University, Department of Computer Science

Title: Asymptotic representation of the average number of active modules in an n-way interleaved memory.

Author: Rao, Gururaj S.

Date: April 1974

Abstract: In an n-way interleaved memory the effective bandwidth depends on the average number of concurrently active modules. Using a model for the memory which does not permit queueing on busy modules and which assumes an infinite stream of calls on the modules, where the elements in the stream occur with equal probability, the average number is a combinatorial quantity. Hellerman has previously app oximated this quantity by $n^{0.56}$. We show in this paper that the average number is asymptotically equal to $sqrt{\frac{\pi n}{2}} - \frac{1}{3}$. The method is due to Knuth and expresses the combinatorial quantity in terms of the incomplete gamma function and its deriviatives.

http://i.stanford.edu/pub/cstr/reports/cs/tr/74/423/CS-TR-74-423.pdf