Mr. Amdahl Calls the Repairman

Back in January, I reported that my Universal Scalability Law (USL) had been proven to be equivalent to the synchronous throughput of the load-dependent machine repairman queueing model. Although I wasn't lying, what I really had was what we call a "sketch" for a proof. The details needed to be filled in, but that was just a question of finding the time to do it. In May, I found time to write the first draft and thought I would be finished shortly thereafter. That attempt ground to a halt for two reasons (you might want to refer to Appendix A in my GCaP book for the background):

1. Simulations that supported the theorem involved a barrier synchronizer, and for this to work continuously, my colleague Jim Holtman, discovered that the distribution of parallel execution times (with mean 'think' time Z) could only be deterministic (D). That's a special case of the repairman: D/M/1//N, whereas the equations in my proof show quite clearly that it must work for M/M/1//N.
   
2. There's a theorem in queueing theory (Bunday and Scraton, 1980) which states that what holds for the repairman (M/M/1//N) also holds for a more general source of requests viz., G/M/1//N. Since G is a superset of the distributions D and M, this theorem suggests that our simulations probably shouldn't be restricted to D-distributed think/execution times as observed in (1). Or should they?
   

Preposterously Parallel iPods

Here's a question: How many FLOPs in an iPod?

Climatologists, up the road here at LBL, claim that a supercomputer using about 20 million embedded microprocessors, such as those found in cellphones, iPods, and other consumer electronic devices, would deliver useful climate simulation results at a cost of $75 million to construct. A comparable supercomputer could cost closer to $1 billion. Based on a recent post, I'd be wanting to see the front-end compiler system that can upload 20 million processors.

Heathrow T5 Killed by Queueing

The British might seem to be alone right now when it comes to airport system fiascos, but the good ole USA is just as good, if not better, at mangling baggage systems. So, what happened? Well, of all the lame excuses, finger pointing and spin-doctoring for the media, this item caught my attention from a performance analysis perspective:

"But the underground conveyor system became clogged because staff failed to remove luggage quickly enough at the final unloading stage. So the system shut down. It's like a shopper putting too many goods on the supermarket check-out belt."

Because the baggage transfer area is tightly secured (we hope), there are no clandestine videos available from passenger cellphones. However, the following queue-theoretic simulation reveals what likely happened.


Click on the image to start the simulation.

Board from the Back of the Bus (maybe not)

When boarding a tour bus, the driver often tells you to occupy seats at the back of the bus first. This protocol is assumed to be more efficient than filling seats from the front because people block the aisle while stowing their carry-on baggage and thereby impede the flow. So, back-filling is more efficient than front-filling but is it optimal? The same procedure is used by airlines that implement boarding by groups A, B, C, etc. Group A is usually seated at the rear of the aircraft. There are some variants with aircraft boarding (e.g., window seats before aisle seats) that also help to distribute the passenger weight more evenly. The question remains, however, is it optimal?

An astrophysicist recently decided to look into this question more carefully using Monte Carlo simulations and found some surprising results. He unexpectedly discovered that the common rear boarding procedure is actually the second worst procedure, since it is only slightly more efficient than boarding front-to-back! So surprised was he, that at first, he thought there was a bug in his code. Then it became apparent that there was something more subtle going on. MC sims showed that an optimal boarding method was for passengers to board 10 at a time in every other row, since loading luggage requires about two aisles of space. In this way, passengers are either stowing luggage or sitting in their seats, rather than waiting in the aisle, as they do in the other two protocols. Depending on the size of the aircraft, this boarding procedure produces a speed up of 5 to 10 times over the worst case. Of course, disembarking is still LIFO. :-)

I wonder if this result could have applications in the context of computer or network performance analysis and capacity planning?

Why Doesn't PDQ Have a GUI?

Recently I was asked if I planned to create a GUI (Graphical User Interface) for PDQ. I've thought a lot about this over the years and my answer (still) is negatory and here's why.

PyDQ (PDQ in Python) Web Pages Get Updated

For all you Python fans, I've updated the PyDQ web page with more online examples to get you started. For example, the communications network model has been revised to use NumPy inline to solve the traffic equations for the internal flows. Previously, I had solved those simultaneous equations separately using Mathematica.

The online PDQ Manual is also being revised to include PyDQ functions and code examples.