>> The final way to settle the elevator argument would be to run a trace
>> of all three elevators for a week. Log when requests are made and
>> where the elevator is. Then we can have an Elevator Algorithm
>> Bake-Off and see whose algorithm, given the trace as input, can fulfil
>> the most requests fastest (we'd also need to argue about the criterion
>> used for judging entries; throughput vs fairness).

> Someone already did this a few years ago, for an undergraduate
> project. (He monitored the elevators by having people observe their
> behavior on different floors.) As I recall, his result was that the
> simplest elevator algorithm (assign the call to the nearest elevator
> heading in the right direction) worked better than the algorithm
> actually implemented, which tried to optimize based on a hotel or
> business model where there was a "main" floor where most of the
> requests come from. One problem with the main floor algorithm was
> that it was restricted to having at most two floors under the main
> floor (like a basement and sub-basement in a hotel), which meant that
> in Wean Hall the main floor was the third floor.

> Since then, I believe the algorithm has been changed to the simple
> version or some variant. The elevators no longer seem to prefer the
> third floor.

About five or six years ago, an undergraduate did a senior honors project analysing the Wean Hall elevators. It was a great project, and one that instantly became a permanent part of CSD lore (in this respect, somewhat like the list of the three best places to have sex in Wean Hall). People seem to constantly talk about this elevator project, but everyone's heard about it third-hand.

I was there. The student's name was Kinson Ho; I attended his final presentation. Let me try and describe it as best I can remember it. Here is what he did.

First, he had his friends hang out in the halls on the floors of Wean and log traffic data. Then he went and researched elevator scheduling algorithms. For mysterious reasons, the Japanese seem to be heavily into elevator scheduling algorithms -- most of the algorithms he presented were by Japanese authors. This area turns out to be a complex little research niche. There do not appear to be any provably optimal solutions. I remember one of the things he talked about was algorithms that try to spread the elevators. One thing your scheduling algorithm wants to avoid is getting the elevators bunched up together. This gives the effect of having a single triple-sized elevator, instead of three independent elevators. You may reflect upon this pessimisation the next time two or three elevators simultaneously relieve your weary vigil on the 8th floor.

By examining the traffic data, Kinson was able to figure out which algorithm the WH elevators use. Then he went and burned up lots of Vax cycles simulating the four or five algorithms he'd found on his traffic data. No surprises here, just confirmation: the WH algorithm was the worst of the lot. The algorithm's performance was made even worse because it had a notion of a "main floor" where idle elevators return to wait. The WH elevators had this floor set to the third floor. This was actually a reasonable assumption in the old days. The terminal room -- hence the center of the department -- was on the third floor. This was back in the days of communal computing, before we had terminals and then workstations in everyone's office. So a lot of traffic flowed in and out of the third floor. People like Rob MacLachlan can tell you more about this era; it was just dying out as I came into CMU.

Kinson stated at the outset of his presentation that he had started the project with a dream. Clearly the elevators are controlled by some simple microprocessor controller, which in turn is controlled by some ROM. What he wanted to do was figure out why the elevators were so suckful, burn a new PROM with better-tuned parameters or a better algorithm, and replace the bogus chip. Presto -- improved elevator performance. (Safety and insurance issues were obviously to be side-stepped for the greater interests of the community.) Kinson managed to figure out the elevators' sensor and control interface -- it was quite simple, just a couple of bits for each. He also had the data and simulations and knew what algorithm would be the best one for Wean. Then, just when your hopes were up, he showed a slide of the elevator controller.

It was several 6-foot tall bays of relays. Click click click. No possible hope of fooling with it. Kinson went so far as to check with the company (Westinghouse?) to see if they had some upgrade to replace all this garbage with a little controller board. They did. It was outrageously expensive, particularly considering you were buying what was probably a cheesy ten or fifty dollar board. There was no way that CMU would buy such an expensive thing. So, in the end, Kinson was defeated.

My suspicion is that Tygar will fare no better. We're talking some big fucking windmills here.

As a postscript, Ho graduated and is now one of Hilfinger's students at Berkeley, where he did a lot of work on the Spur project.

-Olin

From cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!webb+ Mon Aug 3 16:55:30 EDT 1992

In article <seQs0uG00gua0HQVQc@cs.cmu.edu> Olin.Shivers@cs.cmu.edu writes:

People seem to constantly talk about this elevator project, but everyone's heard about it third-hand.

I was there. The student's name was Kinson Ho; I attended his final presentation. Let me try and describe it as best I can remember it.

1. Requests from main floor going up.
2. Requests from main floor going down.
3. Requests from other floors returning to main floor.
4. Requests from other floors going to other floors.

Hence, a request from, say, the fifth floor going to the seventh floor is given lowest priority.

I disagree with Mary Shaw on the fifth floor being a main floor -- the third floor is the only main floor, because the main floor can have at most two levels below it, as I said. When the building was designed, this was probably thought to be OK since the Computation Center was on that floor, as she said.

More recently, I ran into an elevator maintenance person who said that the algorithm had been changed (though elevators still apparently return to the third floor). Perhaps some of the priority levels were set to be equal, because I do believe elevator performance has improved in recent years.

One interesting side effect of using relay banks to control the elevators is that when Wean Hall humidity gets high (due to air conditioning failure) the elevators behave more erratically than usual: not stopping at certain floors, etc.

-- J

From cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!tygar Mon Aug 3 16:56:41 EDT 1992

I consulted for a major elevator company (not the elevator company serving Wean Hall). The first thing I learned was that elevator companies make little or no money from the sale of the elevator. In fact, the often sell the elevators at a loss. Instead, they make all their money from highly lucrative maintenance contracts. Of course, elevator owners can choose any maintenance firm they wish, so the elevator companies thus have a strong incentive to make their systems hard for others to maintain. An elevator that was easy to reprogram could result in a lot of money lost for the manufacturer.

You don't make money selling razors -- you make money selling the blades.

This is all completely consistent with my experience as a user of the Wean Hall elevators.