nbingham

I'm working on a compiler for asynchronous circuits. Once I have modules, placement, and routing working, I'll have an MVP. Hopefully, this will allow people without any computer engineering expertise to make chips. For now it has a couple of useful tools.

https://github.com/broccolimicro/loom

I tested two C++ implementations of Calendar Queues again the standard library priority_queue. The first implementation uses a deque as a backing container and then fills the calendar with linked lists. The second implementation just uses vectors in the calendar with no backing container.

The calendar queues have an interesting failure mode. If you are randomly inserting elements with a priority that is less than "now", and then pop some number of elements, and doing this repeatedly, then the front of the calendar empties out. As a result, the random insertions create a single value in the front of the calendar, then there are many many days that are empty after that. So subsequent pops will always have to search a lot of days in the calendar. So, these calendar queues are only fast if you keep track of "now" and only insert events after "now".

https://gist.github.com/nbingham1/611d37fce31334a1520213ce5d...

seed 1725545662 priority_queue 0.644354 calendar_queue 0.215860 calendar_queue_vector 0.405788

seed 1725545667 priority_queue 0.572672 calendar_queue 0.196812 calendar_queue_vector 0.392303

seed 1725545672 priority_queue 0.622041 calendar_queue 0.241419 calendar_queue_vector 0.413713

seed 1725545676 priority_queue 0.590372 calendar_queue 0.204428 calendar_queue_vector 0.386992

I worked on a similar project - the Stanford braindrop chip. It's a really interesting technology, what happened is that most people don't really know how to train those systems. There's a group called Vivum that seems to have a solution.

I work with QDI systems, and I've long suspected that it would be possible to use those same design principles to make analog circuits robust to timing variation. QDI design is about sequencing discrete events using digital operators - AND and OR. I wonder if it is possible to do the same with continuous "events" using the equivalent analog operators, mix and sum.

The reason we ended up with digital logic is because of noise. Hysteresis from digital gates was the only way to make such large systems from such small devices without all of our signaling turning into a garbled mess. Analog processing has its niches and I suspect the biggest niche will be where that noise is a feature rather than a hindrance, something like continuous time neutral networks.

Rajit has since moved to Yale and has made quite a bit of progress on the tooling problems

https://github.com/asyncvlsi/actflow

https://avlsi.csl.yale.edu/act/doku.php

https://avlsi.csl.yale.edu/chips.php

There's also a bit of documentation up on Wikipedia now

https://en.wikipedia.org/wiki/Quasi-delay-insensitive_circui...

I think there's been a misunderstanding.

You're right, and I don't intend to condemn all of async, or even QDI for that matter :) I am doing my PhD on it, so I do think there is promise. I just think that arithmetic is better handled by Bundled-data specifically. Let QDI do the control leg-work and tack high-performance arithmetic to it.

Also, Gasp is certainly faster, but is limited to simple pipelines. That's why I like QDI, it lets me make weird circuits.

EDIT: Sorry, I got mixed up between the conversation threads... dislexia is a thing.

I'm not saying condemn async or QDI, but we must recognize what it is good at and what it is not. A QDI pipeline stage may be slower, yes. So don't use it if you just want to implement a linear pipeline. But do use it if you have a complex network because of the previously mentioned benefits. Gasp and other async pipeline topologies don't have the flexibility of QDI, and there isn't really a good framework to mix them with QDI techniques at the moment (maybe relative timing?). The power of async comes from this flexibility and the ability to avoid unnecessary computation.

Ideally, none. We're leaning toward FPGAs and CGRAs to accelerate tight inner loops. This means that it will have a huge effect on compilers. They will have to compile from a control flow behavioral description like C to a data-flow description to map onto the array. This compilation process is honestly not solved. This is why you have verilog instead of just compiling C to circuitry. I've taken a crack at it (in the form of QDI circuit synthesis from CHP) and every sub-problem is either NP-hard or NP-complete.

Though all of this is assuming we solve the memory bottleneck... which... might come about with upcoming work on 3D integration and memristors? who knows.

I was specifically talking about dual rail domino QDI. When you compare the typical dual rail domino QDI adder found in Andrew Lines thesis against a typical clocked carry lookahead adder like Kogge & Stone, it is worse by factors of between 2 and 3 in energy, area, and throughput.

Bundled data is a simple control with data clocked from that control. Its very much keeping arithmetic away from the QDI circuitry.

Though to be fair, I haven't seen a good examination of how pass transistor logic might affect QDI arithmetic circuitry, so maybe there is hope.

Hence my thesis :)

Synchronous design tools are very good at making all of the pipeline stages have about the same logic depth, which is generally 6-8 transitions/cycle but can be much less. The fastest possible QDI circuit is a very simple, very small WCHB buffer which has 6 transitions/cycle. Most QDI logic will have 10-14 transitions/cycle.

Also, the speed of a linear pipeline is limited to the slowest stage in the pipeline whether or not you use clockless. Clockless only helps pipeline speed when you have a complex network.

Yep, I saw that go by, and a lot of my work is heavily influenced by Andrew Lines. But what I've been seeing is that QDI is really bad at arithmetic because the acknowledgement requirements turn XORs into a nightmare hairball of signal dependencies. But QDI is really good at complex control.

> This article is 17 years old and I haven't seen any clockless designs in my professional experience in all of that time.

Yeah, async design takes a while, and async chips don't tend to be well advertised, but they are there.

Async FPGA has 60% less power, 70% increased throughput http://csl.yale.edu/~rajit/ps/fpga2p.pdf

High speed routing (from Fulcrum, one of the startups bought by Intel and shut down) https://www.hotchips.org/wp-content/uploads/hc_archives/hc15...

Ultra low power processor https://ieeexplore.ieee.org/abstract/document/1402056/

Ultra low power neural network accelerator from IBM https://www-03.ibm.com/press/us/en/pressrelease/44529.wss

And the truth is that we are. Here is a bunch of data on Intel's processes that I've pulled together from various public domain sources. The yield curves are a very rough estimate, so take them with a grain of salt.

https://www.nedbingham.com/intel_max_transistor.png

https://www.nedbingham.com/intel_switching_frequency.png

https://www.nedbingham.com/intel_tdp.png

https://www.nedbingham.com/intel_gate_delay.png

Heyo, I'm a PhD student in the field. I figured I can talk about its current status.

First, here are various search terms: clockless, self-timed, delay-insensitive, latency-insensitive, quasi delay-insensitive (QDI), speed independent, asynchronous, bundled-data

There are a wide variety of clockless circuits that each make their own timing assumptions. QDI is the most paranoid, making the fewest timing assumptions. Bundled-data is the least paranoid (its effectively clock-gating).

A clockless pipeline is always going to be slower than a clocked one and requires about 2x the area. However, clockless logic is way more flexible, letting you avoid unnecessary computation. Overall, this can mean significantly higher throughput and lower energy, but getting those benefits requires very careful design and completely different computer architectures.

Most of the VLSI industry is woefully uneducated in clockless circuit design and the tools are terribly lacking. I've seen many projects go by that make a synchronous architecture clockless, and they have always resulted in worse performance.

What this means is that it would take billions of dollars for current VLSI companies to retool, and doing so would only give them a one-time benefit. So, you probably won't see clockless processors from any of the big-name companies any time soon. What they seem to be doing right now is buying asynchronous start-ups and shutting them down.

As of the 90nm technology node, its not possible to be switching all of the transistors on chip without lighting a fire. This mean that the 2x area requirement is not much of a problem since a well-designed clockless circuit only needs to switch 25-50% of them at any given time. Also since 90nm, switching frequencies seem to have plateaued with a max of around 10 GHz and typical at around 3 GHz. When minimally sized, simple clockless pipelines (WCHB) can get at most 4 GHz and more complex logic tends to get around 2 GHz (for 28nm technology). Leakage current has become more of a problem, but it's a problem for everyone.

There is a horribly dense wikipedia page on QDI, but it has links to a bunch of other resources if you are curious.

Here is the counter argument to Stochastic Computing.

http://csl.yale.edu/~rajit/ps/stochastic.pdf

Basically, stochastic computing takes exponentially more time and energy to perform the same computation at the same precision, and has a higher error rate. If you want to save energy on precision, it would be better to use bit or digit serial operators.

Note of disclosure, this paper was written by my adviser and I am currently writing two papers on digit-serial arithmetic operators.

Range-v3 seems to be solving a different problem. It seems to be introducing support for Pythonesque features like type-checking and list-comprehension. However, the algorithms that are documented still use first/last iterators (http://en.cppreference.com/w/cpp/experimental/ranges/algorit...). There seems to be a set of basic range class definitions and there seems to be a View class, but I'm not sure if they interact to provide the same type of generic slice definition that I've developed here.

Perhaps I am missing something though, could you expand a little on the specific part of Range-v3 that you are thinking of?

Inheritance as implemented by Go provides for a different school of thought from C++. In C++, you define the taxonomy, then define the objects in relation to that taxonomy. In Go its the opposite, defining taxonomy in relation to the objects.

In concrete terms for C++, this means that abstract base classes Must be defined before the objects are defined. So if I wanted to use a library, I would be entirely restricted to whatever abstract base classes they define.

For Go, I could use a library and then define whatever interfaces I needed specifically for the functions I want to implement. Its effectively a much more structured and rigorous architecture for templated code.

At least this is my understanding. I've explored Go just enough to get some of the higher level concepts but I haven't quite dug into it yet. So correct me if I'm wrong.