6 Apr
2009
6 Apr
'09
6:18 p.m.
On 6 Apr 2009 at 13:48, Paul Koning wrote:
Some of this stuff still makes sense. You still need
external sort to
sort really large data files, and algorithms that access the external
files sequentially are still winners even with disk files.
Or bulk core. Sometime during the 70's, a fellow worker and I were
teamed to produce a sort that could make efficient use of what was
then large amounts of ECS. It was an attempt to salvage the utility
of the installed ALS hardware, where every installation had at least
2M words of ECS--and some had 4M. The volume of data to be sorted,
however, was much larger than this, necessitating an external sort of
some kind.
We thought that surely, with a large fast random-access medium, we'd
be able to improve on traditional tape external sorts. After a
couple of weeks of scribbling on whiteboards and headscratching, the
conclusion was that, no--the traditional external sorts were really
pretty good even with bulk core. I recall both Flores and Knuth
(with the fold-out tape motion charts) were around much of the time.
(For those unfamiliar with CDC architecture, ECS was an external bulk-
core device with significant transfer initialization latency, but
once going, could transfer a block at full memory bandwidth. There
were only two instructions--read and write--to access it) ECS could
also be shared by several machines, which for our project, made it
particularly valuable.)
--Chuck