Alan Jay Smith was a consultant for a company I worked for in the late 1990s. Very smart guy, already seemed "old" to me then, but he was quite a bit younger then than I am now. Geez. He worked on processor architecture, but his most influential work has been on storage systems, and here in 1981 he was already deep into what became known around this time as hierarchical storage management (HSM) systems. Even well before this article, though, mainframe computers used a combination of hard disk and tape to hold user files (as in the figure above, taken from this article) that were considered active; if your file had suffered the unfortunate fate of being evicted from disk, when you asked for the file, it had to be fetched from tape -- a task that could take a couple of minutes up to an hour, depending on whether tapes had to be fetched and mounted by a human. Alan worked on understanding inter-reference patterns, hopefully reducing the incidence of that unfortunate fate. He found that not only was it a long-tailed distribution, with many files never accessed beyond two days after their creation, but among those whose active lifetimes were long, some showed periodic use that could be predicted and taken advantage of. Modern server and storage farms operate at a scale and level of parallelism inconceivable in the 1970s and early 1980s, but I wonder how many of the designers of today's systems are familiar with the foundational work done by people like Alan Back in the Day.
Preparata and Vuillemin described CCC, Cube-Connected Cycles, as a compromise on the physical infeasibility of a large-scale hypercube interconnect. They limit the overall structure two an ordinary three-dimensional cube, with each vertex replaced by a ring of nodes sufficient to make up the extra dimensions; i.e., if what you want is a 5-cube, the overall structure gives you 3 dimensions and each ring emulates 2 dimensions, so each vertex is replaced with a 4-node ring, as in the figure below. Later analysis by Dally would propose k-ary n-cubes with small n instead of this somewhat more irregular structure.
Lamport proposed a password authentication system in which the terminal actively participates; the user identifies themselves to the computer, the computer issues a challenge (from a predetermined challenge sequence), the terminal calculates the challenge using the user-supplied password. With this scheme, the computer (or server, in a modern client-server system) never holds the password or enough information to allow an eavesdropper to create and crack the next iteration of the challenge. Of course, this requires that the terminal (client) itself be secure. I'm not enough of a cryptographer to know how influential this particular paper is, but it's worth noting that it comes five years after Diffie-Hellman (one of only two references in this "Technical Note" short paper).
David Patterson implemented a high-level language, called STRUM, for microcoding a Burroughs D-machine. I have done very close to zero microcode myself (one student project during my master's degree, and reading some VAX microcode around the same time), though I suppose things like SCSI processors and network packet processors are about halfway in between ordinary instruction sets and microcode. Microcode programmers are Titans of the old gods; it's a very early idea, attributed to Maurice Wilkes himself. I don't think Patterson's approach ever really took off; as far as I am aware, writing microcode still involves very low-level management of latches and data routing and the like, not really amenable to high-level languages, in my opinion. Interesting project, though. (Interesting side note: this article took over two years from initial submission to acceptance.)
One article I read as a grad student is Stonebraker's Operating System Support for Database Management. Today, it reads like a fairly basic, almost plodding analysis, but it was groundbreaking at the time, and in my own field this kind of clear-eyed analysis of how good a job quantum hardware and software do for particular tasks should become standard practice.
Overall, I have to say, not CACM's most exciting year.
No comments:
Post a Comment