Negative delays: not in VB (Lucian Wischik)
Our recent post on “negative sleeps in VB” was an April Fool’s joke. VB doesn’t have negative sleeps, and isn’t going to. But the joke’s on me! Several readers wrote back to say that other languages do have negative sleeps. Tony Hoare, inventor of “Quicksort” amongst other things, wrote:
Did you know that negative delays have long been used in practice in the design of systolic circuits? The negative delay is used to synchronise signals in the middle of the network, just like a positive delay. There are a series of commutation laws that allow delays to be moved before or after a circuit element. A negative delay can then be cancelled by an adjacent positive delay.
Of course in hardware design, all these cancellations have to take place at ‘compile time’, before the circuit has to be printed on silicon. I expect that software compilation technology is sufficiently advanced to enable these negative waits to be similarly resolved at compile time.
Another long-standing hardware application of the idea is more dynamic. In the instruction pipeline of a modern architecture, the highest latency is on memory reads. So whenever the instruction decoder meets a read instruction, it executes it after a negative delay, with an interval automatically adapted to deliver the answer ‘just-in-time’.
I do recommend the infinite negative sleep extension suggested by Albert. It is the first approach that I have seen to a wish fulfilment machine: anything we might ever want has already happened an infinite time ago!
Actually, Tony started his email with a joke that he’d initially discovered a “VeryQuickSort” algorithm whose expected cost was O(-n) rather than QuickSort’s O(n.logn), unfortunately not reproduced by other researchers — so I didn’t know whether he was also joking about negative delay elements. It turns out that he wasn’t!
Negative delay elements were used in Ruby, a hardware description language developed in Oxford and Glasgow in the 1990s. The following diagrams are taken from its documentation [Ruby-1-90.ps.Z – extract using “gunzip” or “uncompress”]. The task is to build a circuit where at each time-step it adds adds up a result from the previous time-step:
The documentation first gives this circuit diagram. The “curved D” blocks are delay elements, so that the result from the previous time-step arrives at the right time:
Then using negative delay elements (back-to-front D shapes) they redesign the circuit like this:
What does it mean in practice? Hardware designer Shay Ping Seng explains:
Ruby has a concept of a negative delay element, which is really useful when you are algebraically factorizing a Ruby expression to retime/pipeline a piece of hardware — but gets a little annoying when you are trying to map the expression into real hardware. What usually happens is that real delays are added to the inputs or outputs of I/Os that have negative delays.
Concurrent programs wait faster
The honest answer for how to make your programs more responsive is that they have to be concurrent and asynchronous. This presentation of Tony Hoare’s is interesting: “Concurrent Programs Wait Faster” [download PPT]. The burning question is how can we, as language designers, make it easier for programmers to write concurrent and asynchronous programs? We’re busy brainstorming on this now for future versions of VB and C#.
Light
Dark
0 comments