Abstract
This paper presents the design and implementation details of the pipeline merge sorter with string(run) length tuning mechanism.
Generally we lose some flexibilities at the expense of the high performance when some function is implemented by hardware. As for sorting, the length of record is the most crucial parameter. The hardware sorter can sort very efficiently the records of a given length determined by hardware. Its performance deteriorates largely, however, when the length of the input record is different from the predetermined length. For this problem, we developed the “String Length Tuning Algorithm”.
In this paper, the architecture and design details of the pipeline merge sorter which implements string length tuning algorithm is presented. We have constructed the 18 stage pipeline sorter. Its memory capacity is 8 Mbytes. The sorting speed is 4MBytes/sec. 256K records can be sorted at one time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Kung, H.T.: The Structure of Parallel Algorithms, Advances in Computer 19, Academic Press, 1980.
2] Yasuura, H.: The Parallel Enumeration Sorting Scheme for VLSI, IEEE, Trans. Comput. Vol.C-31, No. 12, 1983.
3] Tanaka, Y. et. al.: Pipeline Searching and Sorting Modules as Components of a Data Flow Database Computer, IFIP 80, 1980
Todd, S.: Algorithm and Hardware for Merge Sort Using Multiple Processors, IBM J.R&D, 22, 5, 1978.
Zeidler, H.Data handling and dedicated hardware for the sort problem, Database Machines, Springer Verlag, 1983(Proc. of IWDM-83).
Kitsuregawa, M. et.al: Architecture and Performance of Relational Algebra Machine GRACE, Int.Conf.on Parallel Processing 84, 1984
7] Kakuta, T. et.al: The design and implementation of Relational Database Machine Delta, Database Machines Fourth International Workshop, Springer Verlag, 1985.
8] Torii, S. et. al.: A Relational Database System Architecture Based on Vector Processing Method, Proc. of 3rd Int. Conf. on Data Engineering, 1987.
9] Kitsuregawa, M.et.al: Organization of Pipeline Merge Sorter, Trans, IECE Japan, J66-D, 1983. Its English translation is available in scripta electrónica japónica III, vol.14, 1983.
Kitsuregawa, M. et.al: Memory Management Algorithms in Pipeline Merge Sorter, Database Machines Fourth International Workshop, Springer Verlag, 1985.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1988 Kluwer Academic Publishers, Boston
About this chapter
Cite this chapter
Kitsuregawa, M., Yang, W., Suzuki, T., Takagi, M. (1988). Design and Implementation of High Speed Pipeline Merge Sorter with Run Length Tuning Mechanism. In: Kitsuregawa, M., Tanaka, H. (eds) Database Machines and Knowledge Base Machines. The Kluwer International Series in Engineering and Computer Science, vol 43. Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-1679-4_7
Download citation
DOI: https://doi.org/10.1007/978-1-4613-1679-4_7
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4612-8948-7
Online ISBN: 978-1-4613-1679-4
eBook Packages: Springer Book Archive