Minimizing Page Fetches for Permuting Information in Two-Level Storage Part 3. The Paging Model : a Further Improvement on the Floyd Model

概要

論文の詳細を見る
Part 1 of this paper (this journal, Vo1.6, No.2, pp.74-77(1983)) discussed the generalization of the Floyd model. In this sequel, Part 3, an attempt is made to remove the artificial restrictions inherent in the previously-discussed Floyd model, thereby giving a nontrivial lower-bound to the number of page fetches in a more realistic computational environment. The findings are that the Floyd-model lower bound is reduced by about half, that an algorithm of transposition can in fact be constructed that can do with fewer page fetches than the Floyd-model lower bound and that, hence, the Floyd model is merely an approximation to realistic situations. The Floyd model, inexact as it is, is nevertheless a fairly good approximation of practical importance, because it is easy to analyze and because it incurs only an admissible error of a factor of two at most. In the process of its design, the algorithm of transposition has been found to possess an interesting property of recurrence, whereby the process of transposition can be decomposed to a host of smaller transposition problems. By use of an evidently superior transposition algorithm at the very lowest level, the overall performance of the total transposition algorithm can therefore be significantly improved with regard to the number of page fetches.
一般社団法人情報処理学会の論文
1985-10-21