Pete's Log: I like reading!!!

Entry #1146, (Coding, Hacking, & CS stuff)
(posted when I was 23 years old.)
So it used to be that reading technical literature was something that bordered on the impossible for me. I had a hard time remaining focused on reading, and even when I forced myself to sit down and read something, my retention of what I read was generally low. All very frustrating. But thanks to a little help from medical science, those problems appear to be a thing of the past. So I've read quite a lot lately. The amount of reading I'm doing is probably excessive, but now that I can actually read and understand papers about subjects that interest me, I'm addicted to it. I've also decided to start summarizing papers that were of interest to me and storing those summaries (where else?) in my log. I'm hoping to generate a lot of these summaries.

Currently I'm trying to add summaries of everything I've read recently. My first attempt failed miserably, ending up with malloc needing a reboot. For attempt number 2, I'm breaking this up into several log entries. Most of what I've read is focused around my desire to better understand MTA concepts, as well as to discover how much focus in MTA research has been put on system software issues. So far I've found very little on system software issues in MTAs. The big things that interest me most from that perspective are as follows:

  • Scheduling
  • Resource Management
  • Runtime models, environments, and support libraries
  • Compiler support
  • Protection
  • Internode communication


Each of those topics could be broken down into many smaller pieces, but that's something for a later entry. This entry is about stuff I read. Let's begin.

Multithreaded Architectures: Principles, Projects, and Issues
by Jack Dennis and Guang Gao

This is chapter 1 of the "MTA: A Summary of the State of the Art" book. It was valuable in that it listed several of the reasons for MTA as well as issues in implementing MTA. It covered in detail several MTA projects: HEP, Dataflow, and Monsoon. It also summarized several other MTA projects. I tracked down many of the references listed in this paper as a next step in figuring out what is out there.

Very little was mentioned in this paper, however, of system software issues.

Another issue that I thought of a lot while reading this paper is just how poor the naming conventions in this research area are ... threads, processes, programs, tasks, continuations ... none of these words ever mean the same thing. This seems especially unfortunate from my perspective, since I am currently residing in the funny area between architecture and operating systems, and it's rather common for a term that means one thing in one of those areas to mean something non-trivially different in the other. Any future writing I do is likely to require brief summaries of what exactly I mean when I use a given term. Or maybe I should just make up new terms instead.


An Object Oriented Architecture
William Dally et. al., 12th ISCA, 1985

The idea, as usual, was to design an architecture that would allow some cool but slow language to be efficiently implemented. In the case of this paper, our language is SmallTalk. The architecture is COM, the Caltech Object Machine.

First, this paper states only ideas, really, and indicates that not much in the way of implementation had yet happened. Some performance numbers are given, but they were collected on a simulator for a precursor to COM, not on COM itself. I suppose I could try to figure out if any more work was done on COM, but I don't really care right now.

However, some of the ideas are interesting. In SmallTalk, all methods are invoked by sending messages to objects. This sounds similar to the OO approach in PIM. Also, in COM (and this probably is inherited from SmallTalk) there is a concept of a "context" which is very similar to a "frame" in PIM. One of the major proposals in this paper is a context cache which is intended to speed up method calls and such. This part of the paper seems very relevant.

The two other primary proposals in the paper for the COM architecture are "abstract" or "virtual" instructions, and "floating point" virtual addresses. The abstract instructions are of no interest to me (other than as an amusing idea) and I feel "floating point" virtual addresses is a deceptive name. More appropriate would be a term such as "Variable Length Segment virtual addresses" or something like that. It is an interesting idea, though, but of little interest to me right now.


Architecture of a Message-Driven Processor
by William Dally et. al., 14th ISCA, 1987

An MDP is a processing node for a message-passing concurrent computer. It is PIM like in that memory is on the processor chip, it is designed to support an OO programming model, and message passing is integrated into the processor.

Like the COM described in Dally's earlier paper, strange caching strategies are used to support the OO model. Much of this paper talked about memory layout and such, and I didn't bother to try to fully understand what they were doing. I don't think I'm interested in providing this much hardware support for dynamic type checking and method lookup and such. But it may be something to think more about later.

The other thing discussed in detail is the message processing unit. Things can definitely be learned from this part of the paper. I should read over it again later.

The MDP is sort of multithreaded, in that it has two sets of registers, one for high and one for low priority. So if a message comes in, the processor can handle it with one set of registers without having to back up the other set.

This paper seemed to me to fail to address the subject of protection. In particular, I was intrigued by the priority concept they used for their two sets of registers. The impression I got was that processes could choose their own priority. Granted, there are plenty of systems in which this is acceptable behavior, but I was disappointed that the priority scheme was not elaborated upon.


Fine-Grain Message-Passing Concurrent Computers
by William Dally, 3rd Conference on Hypercube Concurrent Computers, 1988

This paper discussed the J machine. Its motivation is as follows: the natural grain size of a program tends to be short, measured in tens of instructions. However, the grain size of parallel computers (of the time, at least) is large, due to various overheads: network, context switch, etc ... So in order to achieve good utilization, programs must be written at a coarse-grain level, so that overhead is amortized. Dally argues (and I agree) that concurrency can be better exploited if architecture overhead is reduced so that finer grain programs can be executed without incurring huge overhead. To this extent he offers two solutions. Improved networking, and improved context switch handling.

I skipped over the networking half of the paper, because I don't care.

The second half of the paper discussed the Message-Driven Processor (MDP) discussed in the previous paper. This paper didn't really cover anything not mentioned already in the previous paper. However, some things were summarized better than in the previous paper.

One thing I've come to be curious about after reading this paper is if code is interruptible in the MDP. Code can be interrupted by higher priority code, which will use the second set of registers. However, I didn't catch any notion of code at the same priority level being interrupted. In fact, one thing mentioned in this paper that was not mentioned in the previous is that message sends are broken up into several instructions. The "SEND" instruction issues the destination address. The "SEND2" instruction is then used repeatedly to send data. Finally the "SEND2E" instruction indicates that the message is complete and can be injected into the network. I have a personal bias against stateful things of that sort, and am curious as to what happens if code gets preempted in the middle of such a send sequence of instructions ... quien sabe. maybe there is no preemption or interruption of code.

Stay tuned for part 2.