Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!endor!reiter
From: reiter@endor.harvard.edu (Ehud Reiter)
Newsgroups: comp.arch
Subject: Re: Sort Co-Processors
Message-ID: <2967@husc6.UUCP>
Date: Fri, 9-Oct-87 10:39:35 EDT
Article-I.D.: husc6.2967
Posted: Fri Oct  9 10:39:35 1987
Date-Received: Sun, 11-Oct-87 13:55:16 EDT
References: <112@sdeggo.UUCP>
Sender: news@husc6.UUCP
Reply-To: reiter@harvard.UUCP (Ehud Reiter)
Organization: Aiken Computation Lab Harvard, Cambridge, MA
Lines: 38

In article <112@sdeggo.UUCP> dave@sdeggo.UUCP (David L. Smith) writes:
>Has anyone out there ever run across a sorting co-processor?  I was doodling
>around the other day and it seemed to me that a lot of computers spend a
>lot of time sorting things out.  An add-on box that you could stuff things
>into and pull them back out of in sorted order would be real handy.

Lots of people have designed various VLSI sorting chips (this seems to be a
popular master's thesis these days).  I believe that one or two of the
database machine companies may use special sort chips, although I'm not
certain.

However, the main problem with a sort co-processor is that sorting tends to
be an I/O intensive task.  If you're trying to sort 100 MB of data in 1 MB
of RAM, what takes all the time is swapping the data in and out of main memory
(remember, the big IBM mainframes used for commercial tasks tend to have
ridiculously small amounts of memory, like 32MB in a $1 million machine - and
most of the 32MB is probably taken up by MVS ...).  In fact, I believe that
traditionally, database people have completely ignored CPU time and looked only
at I/O time when computing the expected times for sorts, joins, etc.

Some researchers have looked at special disk hardware to speed up database
operations, but I don't believe this has been very successful (I can dig up
some references if people are really interested).

Another problem with a sort co-processor is that it would probably have to
be closely integrated with a lot of memory (a uniprocessor sorter which used
the main memory bus probably would be of only marginal benefit).  This brings
up the standard problem of either having to transfer massive amounts of data
into and out of the sorter's memory, or of having the sorter's memory
somehow be usable as main memory by the host.

So, sorting coprocessors are possible, but the problem goes far beyond
designing clever VLSI comparison circuits, which is what most people seem
to do.

					Ehud Reiter
					reiter@harvard	(ARPA,BITNET,UUCP)
					reiter@harvard.harvard.EDU  (new ARPA)