Wednesday, May 1, 2013

Speculative Execution/Pre-Fetch/Super-Scalar at Starbucks

Waiting in line at Starbucks is sometimes fun because you can think about life or people watch.
But it can also thwart business.

Little's Law tries to predict the average wait in line with

    L = λW

   where

      L is the average time a customer has to wait
      λ is the arrival rate of customers at Starbucks
      W is the average time it takes Starbucks to serve a customer

So if customers arrive at Starbucks at the rate of 60 / hour (or 1 / min), and the college kid at Starbucks can only make 30 lattes / hour (or 0.5 latte / minute, or 2 minutes / latte ), we have:

      L = 1 customer / min *  2 minutes / latte
          =  2 minute wait average

How can we speed this up? Taking some principles from computer science, let's explore the idea of speculative execution, pre-fetch, and super-scalar parallelization.

If Starbucks implement speculative execution, it would probably have fresh lattes pre-made.  If Starbucks pre-fetched, they will send an order taker to find out orders from people in the back of the line. If Starbucks deployed parallization, they will have multiple stations and workers, ensuring that there are no hardware hazard (fancy talk for resource contention - two baristtas waiting on one latte machine).

So for Starbucks, if they can pre-fetch, paralleize, or execute speculabitvely, this will reduce "W", and the result will be:

      L = 1 customer / min *  1 minutes / latte
          =  1 minute wait average

Resulting in more business because a shorter line entices customers, increases throughput (sell more lattes), reduces latency (sell lattes quicker).


No comments:

Post a Comment