HRSA - Close, but no cigar

I came across this PowerPoint about HRSA: High-Speed,
Hierarchical Synchronous Reconfigurable Array which is part of the BRASS Project University of California at Berkeley via a google search.

They figured out that long interconnects are a problem when you're trying to get speed out of a logic array, but don't seem to be willing to give up the big complex interconnection logic.

I'd call this a step closer to the bit grid, but definitely not a hit.

Instruction Systolic Array

The BitGrid is based on the idea of data flowing through a grid of instructions. The logical inverse of this situation is to have the data remain in place, while instructions to modify it flow past it... this is the Instruction Systolic Array.

The idea is intriguing because it offers a way to get the benefits of the systolic array without having to have all of the bandwidth necessary to update all of the cells at once. The web site is well thought out and informative as well. I like the illustration of the matrix multiply using their concept.

There are a lot of architectures that got skipped along the way to our current crop of FPGA and other programmable logic circuits. I think that the systolic array warrants further consideration as well as the BitGrid.

BitGrid - A minimalist systolic array

Sometimes the key to everything is to find the right words... the right words to explain a concept, the right words to feed into a search engine. I've learned some new words to explain the BitGrid, and they help tie it into the history of computing a bit better, and give context. The two words are

systolic array

The bitgrid as I imagined it way back in the 1980s is a systolic array. It takes information, and processes pieces of it simultaneously. It's an extension of the then-common idea of a bit-slice processor, which was used to create really fast custom processors before the microprocessor really took off.

The BitGrid is a minimalist bidirectional systolic array. According to the wikipedia entry on the subject, the pros and cons of systolic arrays are:

Pros

• Faster
• Scalable

Cons

• Expensive
• They are a highly specialized for particular applications.
• Difficult to build

The fact that I want to process 4 bits at a time means that each cell is almost trivial, a 4bit wide 4address line EEPROM table, for a total of 64 bits of information. This makes it cheap and easy to design and build, pretty much wiping out the Cons in the table above. I don't have a way to get silicon, yet but I expect it should be the matter of getting a cell and it's addressing logic right, then replicating a big grid of these onto a single chip.

I've figured out that a n bit multiplier requires n*(n-1) cells. A divider takes the same number of cells. Adding and subtracting n bits requires n cells.

It's amazing how little of this can be found via a straightforward Google search, unless you know exactly which magic words to use. Semantic web searches will add value, should they ever actually get here.

Logisim

Earlier this week I foundCarl Burch's wonderful Logisim which does digital logic simulation. It took a few hours of tweaking, and one flash of insight (below)... but here is what a single BitGrid cell looks like in an idealized format.

The cell consists of a single 16x4 RAM cell (4 bits address, 4 bits data). I used a ROM in the simulation to allow it to persist across saves, and simplify the layout.

There are any number of ways you could wire this thing up... the flash of insight I had was that I wanted it to be very simple to turn a cell into a simple pass-through repeater. I figured that if addresses 0-F were programmed with contents 0-F, and it just worked that way... it would be easiest to understand. This leads naturally to the layout you see pictured here.

If you want to see for yourself, here is the Logisim Circuit file. (You'll have to save it, then rename it to *.circ for Logisim due to limitations of my web host at 1and1.com)

I welcome comments and suggestions.
--Mike--

Signs of life

I ran into Joshua, who might be able to help me get a chip made! He's been through chip design, and is a EE at heart. I laid out what I wanted to do, answering questions along the way... and there were no obvious huge stumbling blocks with what I want to do.

It's not dead yet! 8)

BitGrid in 25 words or less

Get bit from each neighbor
concatenated 4 bit number becomes index
One lookup table per neighbor

Bitgrid pro and con - AKA the Thesis

If the Bitgrid is such a great idea, why haven’t I heard of it before?

One word answer: “Efficiency”

My review of the current literature, aided by my trusty pal Google has shown that the past 25 years of programmable/custom logic design is focused on serving one God, efficiency. All of the designs I’ve seen (admittedly a small subset because I’m not a professional circuit engineer) optimize on some or all of these common goals:

• Speed
• Power
• Size
• Circuit complexity
• Unit cost

They do this for a very good set of reasons. You want the lowest power dissipation because it makes it easier to feed and clean up after. You want the fastest speed because that is the driving factor for using hardware instead of software. You want the smallest design size so that you use less die area, and have less chance of a losing a chip to a defect. The circuit complexity goal drives a huge investment in design tools to automate design tasks as much as possible.

The things that are often traded away for these goals in a chip design are:

• Flexibility
• Fault tolerance
• Engineering costs

The primary reason for going with hardware in the first place is usually speed. If speed is not an issue, then it is usually a good idea to do a given task in software. Software is infinitely malleable, and far easier to patch and update.

Fault tolerance is usually excluded from designs of custom chips because it is difficult to achieve, and is better addressed by testing and quality control measures. Only when a given feature of a design is homogenous such as in RAM or ROM, is the option to include spares included in a design.

Engineering costs are usually considered last in a mass produced chip, but they are never trivial. The processes are optimized to automate as much of the design work as possible away from human engineers, but there are always going to be complexity limitations imposed by the heterogeneity of the elements in a given Programmable Logic / Custom ASIC design.

When viewed from the perspective of the design community I’ve observed, it becomes obvious why nobody has built a bitgrid yet… it’s inefficient as hell by their criteria. An insider would never seriously consider a bitgrid design.

That, gentle reader, is why you haven’t heard of the bitgrid before.

Reasons to consider the bitgrid

One word answer: “Efficiency”

Only in this case, a different set of parameters to optimize on:

• Flexibility
• Fault tolerance
• Testing time
• End users

The bitgrid is based on a single basic component, with a known, easily comprehended design, in an orthogonal grid. The homogenous nature of the grid makes it trivial to relocate a given portion of an application program.

It can route around a bad cell, if one is found. Each and every cell is a programmable wire at minimum utilization. As long as extensive faults are not present, and slack is available, it should be feasible to route around bad cells in almost any design.

Because it’s possible to test the RAM that stores the programming along with the bitgrid cells one at a time, it should be very easy to quickly and confidently test a chip with a minimum of testing equipment complexity.

Because of the simple nature of the bitgrid, a set of graphical tools for design and debugging can be built and will be applicable to any implementation of the chip. The parameters of the IO pins and array size are the main constraints to give to the tools. There are no design heterogeneity obstacles to complicate tool development.

There are, of course some bit trade offs made, including:

• Speed
• Latency
• Power
• Die Size

• Unit cost

Compared to an ASIC, a bitgrid will always be slower, use more power, consume a larger die space and cost more per unit. A given bit will have to traverse at least 4 gates per cell, just to emulate a wire. The end user, will be compelled to expend some time optimizing their programming to fit in the smallest available bitgrid device applicable, of course.

Summary

I’m confident that as Moore’s law continues to drive down transistor prices, the bitgrid will become seen as a viable computing architecture for select applications, and may possibly mature into general use over time. The closest analogy I can evoke at this time is to the debates that were made with the introduction of high-level computer languages. It occurred when the cost of computation was driven below the cost of the programmers. I believe this transition is on its way for silicon.

I believe the best way to predict the future is to invent it. I hope you like my invention.

--Mike—

March 16, 2005