Browse Prior Art Database

AN ON-CHIP COMPARE/STEER BUBBLE SORTER

IP.com Disclosure Number: IPCOM000128165D
Original Publication Date: 1980-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 16 page(s) / 46K

Publishing Venue

Software Patent Institute

Related People

D. T. Lee: AUTHOR [+5]

Abstract

Two generic record-permutation bubble devices - the bubble ladder and the bubble string comparator - have been reported in the liter-ature. The former relies on the extensive use of external control lines while the latter relies solely on bubble-bubble interaction. The ladder has evolved into an odd-even sorter and then a rebound sorter, but unfortunately it is operated by a large number of con-trol lines. This paper shows that equally efficient but more ver-satile sorters can be constructed from the bubble string compara-tors without the control lines. Moreover, the new sorter - an up-down sorter - will be implemented in the recently invented high-density, high-speed, coil-less perforated-sheet bubble devices.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AN ON-CHIP COMPARE/STEER BUBBLE SORTER

D. T. Lee Hsu Chang C. K. Wong

#80-04-FC-02

iDepartment of Electrical Engineering and Computer Science, Northwestern University, Evanston, Illinois 60201.

2 IBM T. J. Watson Research Center, Yorktown Heights, New York 10598. D. T. Lee Department of Electrical Engineering and Computer Sciences Northwestern University Evanston, Illinois

Hsu Chang C. K. Wong

IBM T.J. Watson Research Center Yorktown Heights, New York 10598

ABSTRACT

Two generic record-permutation bubble devices - the bubble ladder and the bubble string comparator - have been reported in the liter-ature. The former relies on the extensive use of external control lines while the latter relies solely on bubble-bubble interaction. The ladder has evolved into an odd-even sorter and then a rebound sorter, but unfortunately it is operated by a large number of con-trol lines. This paper shows that equally efficient but more ver-satile sorters can be constructed from the bubble string compara-tors without the control lines. Moreover, the new sorter - an up-down sorter - will be implemented in the recently invented high-density, high- speed, coil-less perforated-sheet bubble devices.

1. INTRODUCTION

It has been estimated that in data processing centers, over 25 percent of the computer CPU time is consumed by sorting [1). Large volumes of data are often stored in magnetic disk files which do not have any intrinsic ca-pability for manipulating data. The burden of sorting (involving relatively simple logic operations) must be assumed by a CPU (a relatively precious re-source). Half of the files with records to be sorted have sizes in the range of one to five megabytes, but smaller and larger files also exist.

The emergence of magnetic bubble technology has engendered much hope for new sorting devices. The bubble literature is not short of logic and da-ta manipulation concepts. The steady advance of the manufacturing technology has already yielded 10 6 _ bit single-chip memory packages in 1979. Megabyte and larger chips will appear within three to five years, Thus a more serious evaluation is quite in order to assess whether bubble chips are valid conten-ders as storage chips with on-chip sorting capability or as dedicated sorting chips to off-load the sorting function from the CPU.

Sorting requires the comparison of key values of records and the subse-quent rearrangement of the records. We shall examine the capabilities of the most recent bubble devices against these

Northwestern University Page 1 Dec 31, 1980

Page 2 of 16

AN ON-CHIP COMPARE/STEER BUBBLE SORTER

requirements. Of all the permutation bubble devices depicted in the literature, the bubble ladder
[2) is perhaps the most interesting and most persistently investigated. Its structure con-sists of many fixed and equal length loops with a switch linking each pair of adjacent loops. By setting switches individually with exte...