Sunday, 10 February 2013

Smart exchanges - speculative transmission


Here is an interesting patent filed in September 2009 by some clever inventors, Liberman, Colligan and Raitsev and assigned to the CME.

The CME patent abstract is a reasonable summary.  The exchange proposes generating likely orders that have not yet occurred and sending them to itself.  It then uses the benefits of already having done some of the work to process its trades more efficiently if the "prediction" was correct when a client order is actually received.  A simple and elegant idea.

The idea of compute, network and other I/O speculation to improve latency and throughput have been around for some time, indeed over twenty years, but popular generic thinking in the area didn't really come into vogue until a little less than a decade ago.  I think Lampson's notes in around 2006 helped drive some the popularity with respect to thinking about the problem in a generic sense.  Such techniques have been around for some time and indeed if you're using an Intel or AMD processor reading this your likely to be using a form of speculative value prediction as well as out of order superscalar execution and branch prediction techniques.  There is an amazing amount of technology used to send songs about how wrong it is to wish on space hardware around the world.

The first I heard about such techniques for option trading were whispered rumours or folklore about Hull or CRT (please remind me about who was first) using pre-computed option pricing sometime prior to my stint working at Susquehanna.  The first time I implemented this kind of technique was there to help with option arbitrage but it was not really new or novel, just new in implementation to Susquehanna (plenty of prior talk but not given priority) at the time.

Similar things are happening in the network device space too.  Cut through switching which is somewhat speculative, as you don't know your data is valid, has been around since before the Inmos C104 and Kalpana (now Cisco) cut through switches of the 90s.  More recently, firms have been proposing devices that go further and are truly speculative in that they make a prediction and pre-emptively start doing a new thing in advance of receiving anything.  The Musoll patent, filed in 2008, on behalf of MIPs, is an example of such prediction and speculative processing.  I do wonder about such patents as it just seems good housekeeping to an extent.

Speculation and getter faster is done by guessing what you have to do and doing it and having a valid escape route for when you're wrong.  Transactional memory is one of the latest examples of this.  Version controlled databases as an alternative to locking were an earlier example.  Indeed in the dark ages of the 70s and 80s optimistic concurrency was an apple not far from this tree. Intel's Haswell will have new ops for transactions.  File systems, memory systems, network systems, compute systems can all benefit from thinking differently and laterally about problems.  Breaking through the erroneous mindset Knuth instilled in many of us regarding "premature optimization is the root of all evil" is important.  The architecture of the whole system matters and it is not a simple optimisation point.

Happy speculating.



__________________

Some further links: