Wherein Mike Warot describes a novel approach to computing which follows George Gilders call to waste transistors.

Thursday, October 28, 2010

Applications - image processing, survey plane

One of the long term issues with having a technology, which should be much more powerful than existing hardware is finding an appropriate use scenario for it.  Today one occurred to me on my commute.

I've been doing a lot of experimenting with synthetic focus imagery. Having recently written a tool to help me do image matching, I've begun to appreciate why Hugin gets so bogged down generating and matching control points. The cross correlation of 2d image sets is a huge resource hog. Fortunately, the bitgrid  should be quite capable of handling it, because the computations are data local, with the only global data being the source material which loads once per frame, and the output maximum coordinates, again once per frame.

I imagine a remote control glider with a pair (latter an array) of cameras feeding into a system which correlates the images to generate altitude data. It should be possible once this 2d triangulation is done, with hints from the navigation system, to then generate a 3d image of the area below, with altitude information at least as accurate as the pixel resolution allows.

If the plane is slow and stable enough to allow multiple overlapping images of the same area, it should be possible to derive super-resolution images using Richardson-Lucy deconvolution.

It all hinges on the question of power consumption of a single bitgrid cell. Something I don't know, but an experienced IC designer should be able to figure out on his lunch break.

Saturday, August 14, 2010

Spreadsheet iteration and other linguistic hits

I continue to search for ideas that are close to the BitGrid, and I've come across Amir Hersch's mention of the need for a "spreadsheet iterator" in his blog post titled "More versus Faster"... the BitGrid would be a good spreadsheet iterator.

I'm still trying to figure out the cost/benefit ratio of getting rid of all routing in an a real world FPGA device. As an abstraction tool, it's totally cool and cost effective, as there are no static or dynamic power costs in a thought experiment. 8)

As an intermediate stage of compiling a design, there are time costs in translations, but they might be worth it when it comes to the ability to move elements of a system design orthogonal to other design decisions.

Time and persistent effort to get the questions answered will tell. I'm glad I'm still asking questions and pursuing the goal of getting a BitGrid chip built

Oh... another linguistic hit  "hardware spreadsheet" as mentioned here.

Tuesday, July 27, 2010

Reconfigurable Systolic Array

I've been searching, and searching, and searching for anything that matches the Bitgrid in architecture... and I've found nothing... today's Google search is reconfigurable systolic array.

I get a lot of results, mostly academic (which means they are behind a paywall, and thus worthless). It does give me a better way to describe the bitgrid, though.

The bitgrid is a fine grained homogeneous 2d reconfigurable systolic array and/or mesh. It will be verified as to utility by simulation. I hope to popularize it with blogs, social media, and making a game out of it.

It is my belief that the flexibility of the LUT based approach more than makes up for the lack of dedicated routing and compute blocks.  Any inactive elements of the circuit are unclocked, and thus should be at very low power.

I'm not sure if I'm going to be a good fit for the OHPC project or not, I've got until August 6 to write a proposal.

Friday, July 09, 2010

Prior art - non found... and I've got a headache

Every single article I checked trying to find a pure LUT based FPGA had some sort of routing fabric in it.

I can't find anything that is close to the bitgrid.

I'm going to try to relax, and wait for the Excedrin to kick in.

Tuesday, July 06, 2010

Learning about chip design

I really need to find out how much power a BitGrid cell will consume, in order to find out how well it could realistically deliver on the Exascale challenge. This is forcing me to learn all about VLSI design. Thanks to CMOSedu, I'm getting up to speed on Electric and LTspice right now. I hope to learn enough to have an answer within an order of magnitude this week.  I'm hoping I can get it in the range of 1 pJoule/operation/cell for a naive design. This would allow a 1000x1000 chip to operate at 1 watt at 1 Ghz.   I expect static power to be very low.


I've got a month until the first DARPA deadline for submissions...

wish me luck.

Sunday, July 04, 2010

What's required for Exascale

I've been watching the google results for the key word "Exascale"... and found this at the bottom of this article about bioinformatics. (Emphasis mine)

And in another opinion piece over at International Science Grid This Week, Irving Wladawsky-Berger, a 37-year IBM veteran, lays out some of the big challenges on the way to achieving exascale computing. Whereas the evolution from terascale to petascale went smoothly using tens to hundreds of thousands of processors from the PC and Unix markets, they will not get us to exascale, writes Wladawsky-Berger. Exascale will require some other kind of major transition in chip architecture, not to mention a completely new programming paradigm
Well... that is precisely describes the Bitgrid, or will, once I get the thing built.

Thursday, July 01, 2010

SimGrid - Up and running

I managed to get a Grid Simulation working.... here is a screenshot of it. I named it SimGrid, and it works in conjunction with Sim01 as a programming tool. First you work out your entry on Sim01 for a single cell, then paste the hex code into the appropriate cell in the Grid. The code to generate it can scale to arbitrary dimensions, limited by the screen and Windows resource handles.

In this simulation, every cell is loaded with the code required to pass each bit through the cell, and have it emerge on the opposite side. Its a fairly easy way to check for logic flaws in the simulator. Here we see a bit from the left side propagating all the way across to the right.

I feel that it's reasonable to estimate I can emulate an arbitrary grid of these, even as many as 1000x1000 without problem. The problem now is to find a problem domain that is appropriate for the architecture to use as a baseline for performance evaluations. I need to make sure it's going to be quick enough once cast into silicon to have any commercial value. I'm hoping it will be fast enough for the Exaflop realm, but I have to real way to tell at this point in time.

I'm starting to dig around for silicon simulation resources, as well as a place to do fabrication of this as an ASIC should I find funding.

I feel like Tesla probably felt when he got the idea of polyphase power straight in his head.... BitGrid has enormous potential, but now is the time for a lot of blood sweat and tears to make it come into being.








Wednesday, June 30, 2010

Unrolling programs instead of loops

A programming trick that used to work was to unroll loops, to prevent the pipeline penalties that occur when you branch. It worked well for a while. The bitgrid is based on the idea of unrolling the whole friggin program. Instead of making a list with less branches... why not distribute each and every instruction of a program out into a physical processing instance?
To make it feasible in hardware, use the simplest computing grid feasible, a grid cells (each cell having 4 inputs (one bit from each neighbor), 4 outputs (one bit TO each neighbor) and a 16 entry look up table), each of which is a pitiful unit of computation by itself.... in a grid size to fit the application at hand, they can execute all of the instructions necessary to compute a result simultaneously.
Communication isn't shared, because every input and output only has 1 place to go or come from. It only has to go to the next cell... so there are no long communication lines to worry about. Each cell can function as a router and logic element at the same time.
Programming is a matter of setting the values in the lookup tables, which could be made of static RAM cells.

Monday, June 28, 2010

Introducing Sim02


Now that Sim01 is capable of demonstrating how a single cell works in terms of bits, it's time to start building a grid simulator. This is my first effort at it. Using Sim01 to figure out the hex codes (a new feature I added to support this)... I was able to determine the proper codes to do a pass through... and make that the default for this 2 cell array.  

Here you see an input from the West side of the array propagated all the way through to the east side. Simultaneously an input from the North of Cell 01 (right cell) is propagated to the bottom.

It's all prototype code, but it is functional. I intend to scale this up to a simulator capable of simulating an arbitrary size grid. Then I'll add some input and output functionality to allow the processing of real data with a simulated bitgrid.

Thursday, June 24, 2010

Introducing Bitgrid-Sim version 0.03

I've created a basic simulator for 1 cell of a bitgrid. The simulator currently is a Windows only application, but it's should be fairly easy to port to Linux should it be required later. Here's the first public screen shot:


The simulation shown is a pass through.... in this configuration the bitgrid cell acts as an expensive set of wires, passing signals straight through. It's useful for filler between active cells.

In this simulator you can edit the program (showing in the 4 areas of check boxes) and simulate inputs The checkboxes corresponding to the current set of inputs are highlighted red as a programming aid. You can save your work as well.

Users can load a few examples, or create there own.  In addition to creating a Google Code project site for it, I've also packaged up the Source, Executable and Examples and made it available as a zip file. It's small, and you just unzip it, and it should be ready to use.

Wednesday, June 23, 2010

Beyond the Petaflop - How Bitgrid could meet DARPA's needs ahead of schedule.

I found this story about a new DARPA request for proposals via Digg. The challenge is to build a computer system which can process 10^18 floating point operations per second. Here's the back of the envelope calculation I posted in response:


I think it could be done in 3 years if it didn't have to fit in one rack, it could have already been done, had there not been such a heavy emphasis on the Von Neuman architecture for the past 40 years.

Imagine a bit slice processor....with perhaps 1000 transistors. Put those in the same die in a 1000x1000 grid, this would require    10^9 transistors. You could clock them at the nice sane clock speed of 1 ghz. That would fit in a die the same size as a current generation cpu.  That's 10^6 slices times 10^9 cycles/second, or 10^15 bit computes per second, on a practical size die, with current technology.

Even if you lost 99.9% of the compute efficiency in shuffling bits around to do a floating point operation, you could still do 10^12 Floating point operations per second, on a prototype chip... today.

The chip would be easy to test, because all of the bit slices would be identical, so the testing of each part could be done in parallel... perhaps 1 second to test time per die. (Testing is a big part of cost when it comes to chips)   The chip would cost somewhere around $10 each.

If you allow me to continue with my estimate of 10^12 flops per chip, and it were possible to build a grid of 1000x1000 of them... that takes you to the magic 10^18 Flops that DARPA wants, for a cost of about $10,000,000.

10^18 operations per second, with 10^15 transistors, clocked at 1Ghz.  Feasible... yes... but it does require you to give up sequential programming, and think in terms of graph flow.

It's called bitgrid, I thought of it around 1981.... and I've written some of this up at  http://bitgrid.blogspot.com

Wednesday, April 07, 2010

Enabling technology on its way from HP

HP has continued to make progress on their Memristors, and this latest advance which allows them to be put into large arrays would be perfect to use as the latch / demultiplexor components of the bitgrid cell. It would be amazing to have a bitgrid with 1000x1000 bits operating at 1 Ghz.

About Me

My photo
I fix things, I take pictures, I write, and marvel at the joy of life. I'm trying to leave the world in better condition than when I found it.