Jeff Barr's Blog

Things I Like..

Airport Security and Pipelined CPUs

I seem to spend far too much of my working life waiting in airport security lines. It doesn’t help that I am based in Seattle, which for a long time had the distinction of having the slowest security lines of any major US airport.

I’ve watched a number of security lines in action, and I have some ideas about what makes certain lines or cities fast or slow. I started to realize that there are analogies between what happens in an airport security line and how a modern CPU (Central Processing Unit) handles a stream of instructions. It seemed like it would be fun to explore all of this by writing it down, and that was the genesis for this post.

Ok, so I’ve only seen two things that seem to help:

  • A guy with a loud voice constantly shouting out directions, information, and exhortations to keep things moving. This is the case in San Francisco.

  • Extra long tables before the metal detector. I’ve seen this work in several airports, including (finally) Seattle and Honolulu. Honolulu made things even better by pre-stocking the tables with loads and loads of the gray baskets.

The second item is what interests me the most, so I decided to figure out why this seems to work so well. First, let’s break down the set of steps that one must go through in order to get through security:

  1. Get boarding pass checked against your identification.
  2. Advance to the table.
  3. Remove laptops, shoes, belts, jewelry, and outer garments, place them into the baskets, and placing the baskets on the conveyor belt.
  4. Step through the metal detector.
  5. Wait for items to pass through X-Ray.
  6. Retrieve items from the conveyor belt.
  7. Put everything back together.
  8. Walk away.

In the worst possible case, one person could go through this entire process at a time. From the time that they get their boarding pass checked until the time that they walk away, the entire system would be dedicated to serving them and only them. Indeed, this is how early microprocessors worked. The processor had just enough logic and complexity to be able to do one thing at a time. The system (processor or security) runs at no better than the speed of the slowest step, and at any given time much of the system’s functionality is simply idling, while some other part is active.

To speed things up, the airport security system can pipeline, or allow more than one person to be in the process at any given time. There’s some implied serialization because certain steps can only accomodate one person at a time. Again, this is what a modern microprocessor does. One piece of the chip is fetching new instructions, another is decoding already fetched instructions, a third is executing those instructions, and so forth. Complex processors can have even deeper pipelines than this, but the general concept is what is important here. Now things can run a lot faster. Returning to airport security, one person can be in each step at each increment in time. In theory, if we have 7 steps, then we can have 7 operations in progress simultaneously, and things can run up to 7 times faster than in the worst case example that I described in the previous paragraph.

Another way to speed things up is to use parallelism. Despite the fact that people have been waiting to get up to the table for 5 to 20 minutes, they still wait until the last possible moment to untie their shoes, remove their belts, and so forth. Some people travel light and have almost nothing to remove, others travel heavy and can spend 2 minutes ditching their watch, wallet, keys, phone, belts, laptops, gold chains, and so forth. There’s room for lots of parallelism at the unloading table, and this is where the good airports seem to have an edge over the bad ones. Longer tables and a ready supply of baskets leads to far better throughput. This also brings to mind another principal of highly pipelined processors, namely out of order execution. If person 1 steps up and takes 2 full minutes to unload, but person 2 steps up and takes just 30 seconds, then the second person can go through the metal detector ahead of the first one. The best processors can do this on an instruction by instruction basis, albeit with substantial complexity when it comes time to making sure that (to an outside observer) the program actually ran in the order specified by the instruction stream. Airport security doesn’t have this problem, although family members do like to rendezvous with each other after making it through to “the other side.”

There’s another form of parallelism present in most airports, because there’s generally more than one metal detector. These are like having multiple processors on a single system, each machine or processor adding to the overall capacity of the system, with a little bit of overhead to route people or instructions to the next available unit.

In some airports there is some reluctance for people to actually do out-of-order processing. It would be excellent if airports were to make it really clear that this is expected and optimal behavior, and that there’s no need to wait for the person in front to finish unloading.

I did see some speedups happen at Sea-Tac last year, when the only visible change was a lengthening of the unloading area, tripling the number of tables. This definitely supports my theory.

So, there you have it, my 2 cents on why longer unloading tables and more baskets, along with an acknowledgement that it is ok to step out of order, can make the security process a whole faster!