Barbara S. Brawn
Abstract
This sorting study was part of an extensive measurement project undertaken on the M44/44X, an experimental paging system which was conceived and implemented at IBM Research in order to explore the virtual machine concept. The study was concerned with the implementation of sorting procedures in the context of the dynamic paging environment characteristic of virtual memory machines. Descriptions of the experimental sort programs and analysis of the performance measurement results obtained for them are presented. The insight gained from the experimental effort is used to arrive at a set of broad guidelines for writing sort programs for a paging environment.
- 1 Comm. ACM 6, 5 (May 1963). {The entire issue is devoted toGoogle Scholar
Digital Library
- 2 FLORES, I. Analysis of internal computer sorting. J. ACM 8, 1 (Jan. 1961), 41-80. Google ScholarDigital Library
- 3 HOARE, C. A. R. Quicksort. Comput. J . 5 (April 1962-Jan. 1963), 10-15.Google Scholar
- 4 HUBBARD, G. V. Some characteristics of sorting in computing systems using random access storage devices. Comm. ACM 6, 5 (May 1963), 248-255. Google ScholarDigital Library
- 5 GILSTAD R. L. POLYPHASE merge sorting-an advanced technique. Proc. Eastern Joint Comput. Conf., Vol. 18, Dec. 1960, Spartan Books, New York, pp. 143-148.Google Scholar
- 6 O'NEILL, R. W. Experience using a time-shared multi-programming system with dynamic address relocation hardware. Proc. AFIPS 1967 Spring Joint Comput. Conf., Vol. 30, MDI Publications, Wayne, Pa., pp. 611-621.Google Scholar
- 7 The M44/44X user's guide and the 44X reference manual. IBM Corp., T. J. Watson Research Center, Yorktown Heights, N. Y., Sept. 1967.Google Scholar
- 8 BRAWN, B., AND GUSTAVSON, F. An evaluation of program performance on the M44/44X system, Parts I, II, III. Part I: RC-2083 (May 1968) ; Part II: RC-2275 (Nov. 1968) ; Part III: RC-2276 (Jan. 1969); IBM Corp., T. J. Watson Research Center, Yorktown Heights, N. Y.Google Scholar
- 9 BRAWN, B., AND GUSTAVSON, F. Program behavior in a paging environment. Proc. AFIPS 1968 Fall Joint Comput. Conf., Vol. 33, Pt. 2, MDI Publications, Wayne, Pa., pp. 1019- 1032.Google Scholar
- 10 BRAWN, B., GUSTAVSON, F., AND MANKIN, E. Sorting performance in a paged virtual memory. RC-2435, IBM Corp., T. J. Watson Research Center, Yorktown Heights, N. Y., April 1969.Google Scholar
Recommendations
Tiered Memory: An Iso-Power Memory Architecture to Address the Memory Power Wall
Moore's Law improvement in transistor density is driving a rapid increase in the number of cores per processor. DRAM device capacity and energy efficiency are increasing at a slower pace, so the importance of DRAM power is increasing. This problem ...
Sorting with Asymmetric Read and Write Costs
SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and ArchitecturesEmerging memory technologies have a significant gap between the cost, both in time and in energy, of writing to memory versus reading from memory. In this paper we present models and algorithms that account for this difference, with a focus on write-...
Efficient Sorting and Join on NVM-Based Hybrid Memory
Algorithms and Architectures for Parallel ProcessingAbstractNon-volatile memory (NVM) as a new kind of future memories has a number of special properties such as non-volatility, read/write asymmetry, and byte addressability. This makes it difficult to directly replace DRAM with NVM in current memory ...
Comments