FPGA Computing and Virtualization

Today was my last day at Xilinx. I fly away from the west coast tomorrow morning and head back to MIT to begin my year as a grad student. Hopefully I will emerge unscathed.

I've been thinking a lot about the implications of software virtualization to FPGA computing. I'm intrigued by the idea of implementing a hypervisor in a tightly coupled FPGA/CPU system. I imagine a system with an FPGA connected to multiple memory units and managing the data flow for the various active virtual machines. The software layer of the hypervisor instructs the FPGA to move data to the processor or to function accelerators within the FPGA. The FPGA would probably host the hypervisor agent in order to concurrently manage instructions from the various virtual machines. Instructions non-native to the CPU may either be executed within the FPGA or "decoded" in the FPGA and passed along to the CPU.

If a virtualization layer sits just above the OS layer consisting of a resource sharing scheduler and a dynamic load balancer then applications would be able to take advantage of fine-grained optimizations while running on a virtualized compatibility layer. The key to making a massively scalable operating system is providing mechanisms for high level agents to inherit from low level optimization. A method for agents to manage "costs" and resource sharing provides an elegant optimization strategy that spans across all granularity levels.

some ramblings about stuff

Starting to think out loud:

Taking advantage of paralellism is a necessary step for the advance of computing. Chip-multiprocessors (CMP) and FPGAs enable concurrent computation paradigms. CMPs allow for thread-level parallelism (TLP), where each core contains an instruction cache consisting of the current set of supported functions. Reconfigruable datapath arrays allow for networks of fixed functions to be interconnected through routers to take advantage of instruction level parallelism (ILP). FPGAs offer even finer granularity of control allowing a network of reconfigurable functions often enabling bit level parallelism (BLP) in addition to ILP and TLP.

The granularity of reconfigurability also has implications to data locality. If we have fine grained control over where we may define memory and registers in our array, then we may localize our variables near the operations that use them. Since memory bandwidth is the primary cause of the "von Neumann bottleneck," on-chip data locality provides a solution.

The cost of reconfigurability is the amount of area required per operation, which implies a lower clock frequency and higher power consumption per function when compared to a fixed implementation. Still it is often impractical to have a fixed-ASIC implemenation for all computing functions. Thus we are left to choose between a reconfigurabile chip and a general purpose CPU. A reconfigurable device can often levarage parallelism to achieve a decrease in total execution time and total power consumption over general purpose microprocessing units.

It may not be the case the a reconfigurable device wins over a general purpose CPU. If a CPU device is more suitable for an application it would be wise to use it. A mixed granular structure incorporating reconfigurable logic within an array of microprocessors can maximize performance by alleviating speed issues for explicitly single threaded applications that cannot leverage BLP, ILP or TLP.

My goal is to create a self optimizing operating system for such reconfigurable heterogeneous arrays. Compatibility with current computing paradigms is a primary objective to minimize barriers to adoption. To maintain compatibility the primary application will be a virtual machine server that manages reconfigurable hardware. The operating system seeks to minimize some cost function while executing some set of processes. This cost function should be based on an economic model of computation concerned with metrics such as power consumption or execution time. If real estate can be used to save energy and time then it has an implied value.

The system is managed by a network of agents. Agents are capable of receiving and responding to signals and objects. Signals and objects are related just as energy and mass are related--sometimes it is useful to look at things as waves, and other times as particles. The agents communicate with one another subject to the constraints of some physical environment just as the propagation of electromagnetic waves is constained by the physical hardware.

To understand the interactions of the network of agents with their environment, it is important to have a model of an environment. An environment consists of a set of state variables, a set of accessors, and a set of state evolution functions. State variables are the information we might wish to know about a system for example the temparature at a location, the configuration of a LUT, the contents of a register or the capacitance of a MOSFET. These examples demonstrate that state variables exist with different scope and different domains.

State variables that are static in scope are the physical constraints that may not be altered by the agents of our operating system. For example, the electro-magnetic constant, the length of copper between two transistors in a circuit, the dopant density of silicon, etc. State variables that are in constant scope provide a configuration layer. This configuration layer may be accessed by reconfiguration agents.

It is generally desirable for things to behave predictably so that we can constrain an environment model and adapt to an evironment. However, this does not mean that we may assume absolute determinism; we should provide a means for semi-static and semi-constant variables that permit some randomness. This will provide support for defective or faulty components.

There should be processes that can simulate a particular environment to allow for behavior predictions. There could also be feedback from some of the physical environment to monitor the system and control the system.

Methods for optimizing the cost function include:

process partitioning
resource sharing and recycling
dynamic load balancing
garbage collection
power and frequency scaling
place and route
defragmentation

These processes are "computationally invariant" which implies that they only alter the cost of execution while the system functionality remains the same.

AMD, Sun... Altera

A few weeks ago I wrote an entry titled "Intel, AMD, Sun... Xilinx." In light of a new press release, It would see a more appropriate title is: "AMD, Sun... Altera"

Achronix

Achronix plans to deliver FPGAs that run at gigahertz speeds over a wide range of conditions. They have limited information on their site, but they claim to be using some asynchronous design method, which begs the question: what is being clocked at gigahertz speeds? They got back some silicon prototypes in April and two days later announced a low-power initiative, so I wonder what the power consumption specs of that prototype looked like. They plan on supporting user-programmable speed and power, which has really interesting implications on an operating system.

In terms of economics GOPS/Watt may be a more important metric than GOPS/(Fixed Cost) especially if long device life amortizes fixed costs. GOPS/Watt is most critical in battery powered applications.

Anyway, according to my unified theory of reconfigurable computing, these kinds of devices live and die by software support so we'll just have to wait and see.


--Edit June 10, 2008:
Cornell's Asynchronous FPGA group has Technical papers about the research that lead to Achronix products.

Rapport Inc.

I picked up last month's Tech Review and I discovered this startup looking to make chips with 1000 8 bit cores. The RAMP Project and the RAW project are extremely relevant to Rapport. Looks a lot like they're taking the RAW chip commercial... I hope that they don't blow through all of their funding attempting to manufacture a chip without establishing a software development environment and a market first.

I approach reconfigurable computing as a software problem first and a hardware problem second. It's something I believe makes business sense, given that COTS reconfigurable chips already exist but no real software exists for them yet. Since no one in the FPGA world has come up with a software methodology for reconfigurable computing, it's hard to imagine how new hardware that looks not to dissimilar to an FPGA will somehow enable a new software paradigm. The Tech Review article hit on these issues and it looks like there are some Quicksilver alumni on Rapport's staff, so hopefully they'll leverage their experience in this area.

These chips look pretty cool to me. Hopefully I can "get my shit together" quickly enough and get a team of geeks together to make OS support.

FPGA Community

I just started fpgacommunity.com. Since only like 3 people read this blog, I suppose the community will be small :) This along with fpgawiki.com will soon be hosted on a different server (when I get back to MIT) and then I plan to spread the meme through mailing lists and usenet groups. I think if there was a tighter community of FPGA users and developers, launching fpgaos.com as a community open source project might actually be feasible.

A few people have commented on why I would want to make the FPGA OS open source. The primary reason is that closed source is counter-academic and creates a barrier to adoption by those who would only use open source (meet the Linux community). The major barrier to FPGA computing is the lack of awareness among computer scientists, and closed source software tools exacerbate that problem. Also, open source guarantees that the best developers out there will have access to improve the code.

It may seem that I'd be missing a huge economic opportunity by going closed source, but if I place more emphasis on advancing computer operating system technology, money will almost definitely find its way to creating new applications. Even though transparancy is the goal of the OS, there will be an awful lot of code that could be optimized for concurrent execution even after an OS is complete. This will certainly be a non-trivial task, that will greatly reward those with expertise.

The amount of coding required to build an operating system for a reconfigurable computer is also way too massive to consider building without the concesus and assistance of the wider community. If everyone "agrees" on the OS then everyone will use it too, which means the effort won't have been wasted.

Intel, AMD, Sun... Xilinx?

Article discusses the potential for FPGA-targetted software. Touches upon Intel's EPIC project that was supposed to make the Itanium rule the world. I think the problem is that the scope of the Itanium processor pushed it to far out of reach. FPGAs on the other hand have the nice property of sweeping across many markets, price points and even usage patterns (embedded controller, DSP, HPC accelerator---what I've been calling "versatility value"). A vendor selling rack-mountable black boxes for application specific enterprise computing needs, has only to demonstrate performance/cost improvements for the application in order to be a viable competitor. If an FPGA solution costs less than an Itanium and can get the job done. then why not go with it?

This market is wide and open. Reconfigurable computing could potentially have an enormous effect on the next revision of the internet infrastructure. Lack of developers is the only reason I can see why this hasn't taken off already. Most people who observe these issues would agree that current FPGA tools mostly suck, and that concurrent application development requires some amount of "magical power." Today it would be almost obscene to go into an enterprise software company and suggest that they should target a reconfigurable computer with their application.

Ah, but look at the way things are headed. Multi-core processors. Virtual Machines. Interpretted web interfaces. For much of the web server market it doesn't really matter whose chip you use as long as you can support Linux, Apache, MySQL, and PHP. Throw in Java and you'll get a huge chunk of the enterprise market too... In fact, start with a Java VM to grab some compute intensive financial service companies. Deliver more bang for the buck in that market, and lots of people will start listening...

scratch scratch

someone else's blog. another confirmation of what i've been spewing... i especially like this comment: "...there is something decidedly unsexy about High Performance Computing..."

a supercomputer with sex appeal... maybe if Apple were to brand it.

fpgawiki.com

A wiki for reconfigurable computing. feel free to contribute. feel free to rip articles off wikipedia too. I will start to publicize it more (mailing lists, usenet and such) once I take care of the hosting issues.

coming soon: fpgaos.com -- As soon as I get back to MIT I will be hosting a website on an FPGA and allow people to actively contribute to the development of the hosting platform.

ee times article

EE Times article asks an interesting question in its last sentence. The answer is "I do." I just need a team of 7 to 10 young (not bound to wives/children) hackers who can work 25 hours a day 8 days a week for the next year. This will also require a bunch of mountain dew and maybe some adult supervision--perhaps a $300,000 in initial funding to buy equipment and pay for the mountain dew. Sounds like oh so much fun.

resource sharing

poppy.snu.ac.kr/~ykim/resume/DATE_05.pdf

a concurrent evaluator

standard press release.


been thinking about Virtual Machines and FPGAs. Both of those two terms are increasing in relevance. they will also start to sync up in co-relevance.

i've made some headway on my thesis work lately. i'm working on a "parallel evaluator" for scheme right now that uses multiple evaluators each with their own strategies.

an evaluator consists of:
evaluation-strategy
listening-strategy
parent
children
partners
objective

an evaluator uses it's listening strategy to communicate with its parent, children and partners. the listening strategy assigns priorities to the different ports. The parent spawned the evaluator. The children are spawned by the evaluator. The "partners" are the other evaluators (non parent or children) that the evaluator shares a port with. the objective of an evaluator is its current process.

with this framework i'm going to start to define different ways of computing things. for example: an evaluator might get a request from his parent to do (foo x). he responds with a promise to do (foo x). he might call out to all his partners and children "can anyone do (foo x)" if someone responds and says "i will do (foo x)" when the parent tries to force the promise, he will tell his parent to talk to them for the answer. if he cannot find someone else to do (foo x) he will compute it himself when it is forced. this is the "laziest" evalutation strategy I could think of on the spot.

I need some descriptive language for managing "evaluator teams" in order to handle the complexity of using multiple parallel evaluators. I want to be able to fit notions like combinatorial functions, memory, state machines, datapaths and processing units into this evaluator framework. i made something similar for 6.891 last semester, by creating an array of nodes that acted on their ports, with surface reconfigurability (using "CONFIGURE" messages) however, the most complex functionality I could demonstrate with that was simple arithmetic pipelines.

This gets closer and closer to the "big idea."

--whoa, this blog entry comes up number one on google search for "concurrent evaluator"

drc

article in the register

genetic algorithm for genetic research on FPGA

In anticipation of my impending internship at Xilinx, I have been searching for an appropriate algorithm to accelerate on an FPGA. A good friend of mine in the Broad Institute at MIT sent me an email last week describing the problem of understanding the binding strategies of the transcription factors of human DNA. On many occasions in the past, we have distracted ourselves from homework by talking about FPGAs (my interest) and bioinformatics (his interest). It now seems some collaboration is in order.

Here is the best I can describe the problem: my understanding of the biology is extremely limited, but the underlying algorithmic problem should be clear (my friend is clearly responsible for any biological aspects of this work). Suppose a set of proteins regulate DNA transcription for genes A, B and C but not genes D, E and F, then there must be some a common pattern in the DNA for genes A, B and C that is not in genes D, E, and F. Unfortunately this DNA pattern matching is not necessarily straightforward: it is not simply the case that genes A, B, and C have the sequence "GGACT" in their regulatory region, which is not in the regulatory region of genes D, E and F. The codes may have a more complex "logic" to them. For example, it may be the case that the pattern is of the form "Does not contain (GGATTC or ACCTAG) within 100 base pairs of a code with a Hamming distance of 2 from ACGGTCCGT." If A, B and C match this pattern and D, E and F do not, then this would explain why the transcription factors in question regulate A, B and C and not D, E and F.

After discussing the problem for a while, we came to the perhaps not coincidental conclusion that a genetic algorithm would be best suited for this problem and that exploiting the parallelism and granularity benefits of an FPGA implementation would offer a lot of acceleration potential. For such a genetic algorithm we test populations of "binding strategies" in an environment consisting of a set of genes joined with a 1 or a 0 depending on if the transcription factors in question regulate that gene or not. The fitness of a binding strategy is measured by the number of times the strategy correctly predicts regulation (1) or no regulation (0). As the algorithm progresses, we select the better binding strategies, breed them and mutate them. We may breed two seperate strategies by combining them with a logical combinator or the "within k base pairs of" combinator. We may mutate the strategies by negating them, by changing, adding or removing characters, by adding or removing logical combinators, or by adding "hamming distance of m" conditions (negating the worst performing binding strategy in a population actually makes sense since it is going to produce a more fit member in the next generation). Generally, we would prefer it if our binding strategies were "simple" to avoid overfitting, and there will be a preference for simplicity in the selection strategy.

This problem lends itself to an FPGA implementation since we may implement an entire population of binding strategies and evaluate their fitness in parallel. We may also perform the population breeding process in parallel and reconfigure the system to evalute the next generation. An well designed approach will be able to share logic among binding strategies in a similar fashion as how the Rete algorithm avoids repeating sub-pattern matching. FPGAs have been shown to produce 1000x speedups over CPU implementations for similar genetic algorithms and also shown equivalently absurd speed-ups for pattern matching algorithms. Certainly we will have to test an FPGA impementation against the cluster supercomputer at the Broad Institute.

One neat idea for accelerting genetic algorithms on an FPGA is to use partial reconfiguration to allow dynamic mutation and breeding during execution. If a member of the population is consistently failing after examining only 10% of the environment data, it may as well be killed off and replaced with a child of more successful members of the population. For this specific problem, after a binding strategies fails to predict the transcription factors behavior on 123 genes, we can recycle the hardware it occupies and replace it with the child of a more successful binding strategy. Alternatively, if a binding strategy succeeds 10% more than any other, it may kill off a "weaker" binding strategy and recycle its hardware for one of its children. This may prove a much better genetic algorithm strategy than using discrete generations.

3-D Integration

3-D integration is going to become more and more popular in the next few years. I created a thermal cost function for a 3-D FPGA Place and Route last year for 6.374. Prof. Chandrakasan, who taught 6.374, has been researching a 3-D FPGA. I haven't done any further work on it since the class, but I read an article today about integrated cooling which made me think about it again (I've looked into implementing the thermal FEA on an FPGA, but others have already done similar things). Xilinx is certainly interested in this research. FPGAs have implicit fault-tolerance which means that yield issues associated with 3-D integration can be marginalized (in fact, Xilinx sells their "defective" units as application specific devices).

The remainder of this blog entry was written on 7/19/05.

3-D chips require less wires. As shown in this thesis and paper, 56% less interconnect is required for a 5 layer chip. Wafer bonding has been thoroughly investigated, and processes compatible with standard CMOS are being refined. Tezzaron is using this technology for memory.
The big problems facing the industry are the lack of good design tools and the issues associated with yield and heat. Design tools will be developed as the processes become more refined. Yield issues and heat need to be taken into consideration in the design. Consider if you have an 80% yield on each wafer; when you have 5 layers of silicon--assuming defects are not correlated to the location on the chip, and no defects due to the bonding process--your yield reduces to 33%. Of course, we are able to have more redundancy with more silicon layers, so we can design systems that are fault tolerant (google: fault tolerant architectures. lots of good stuff). The costs of the chips will probably directly represent the decrease in yield -- good designs and tools will save companies a lot of money (though i shouldn't give away my secrets before i patent them :-)

Cooling higher density chips is the major hurdle towards development of 3-D circuits. A few documents hint that microfluidic cooling systems may be the solution. Georgia Tech researchers made an advance on this end a few weeks ago by presenting a microfluidic manufacturing process compatible with standard CMOS

Expect lots of great things in the years to come. For now I expect 3-D integration to creep into specialty mixed signal chips that are extremely expensive, and memory where heat generation is less of a problem. Microfluidic cooling technologies will be adopted in the near term for 2-D high power chips. The first 3-D micro-processor architectures will probably use extra layers for clock distribution, global interconnect systems, and power distribution systems. Caching systems will likely be added as a third layer until new design approaches (and better tools) allow for the design of multi-layer integration with logic interspersed between the layers.

Computing Without Computers

Found this article by Ian Page, a researcher in reconfigurable computing and founder of Celoxica. I think he's right on with his observations.

my daily headache

I've been toying with an IP core that allows me to access the FPGAs reconfiguration port from the internals of the FPGA. I've connected the reconfiguration port to a microblaze core running ucLinux, but I haven't actually got a method to do anything worthwhile. I'd like to get a Linux running on the dual PowerPCs so I can start to Kernel hack it and enable dynamic reconfiguration methods. I'm thinking to develop a "debug" mode that displays a picture of the FPGA on the screen and allows you to see and manipulate the configuration.

Paper of the day:
Operating systems for reconfigurable embedded platforms: online scheduling of real-time tasks
Steiger, C.; Walder, H.; Platzner, M.;
Computers, IEEE Transactions on
Volume 53, Issue 11, Nov. 2004 Page(s):1393 - 1407

This paper got me thinking about the "shapes" of our reconfigurable units. If we only think it rectangles we'll be horribly limiting ourselves, but if we use more complex shapes they will be extremely difficult to manage. This paper uses the term "fragmentation" to describe the wasteful effect of using rectangles and I think it's a good term to pick up. The effect is similar to fragmentation on a hard disk and "defragmentation" will be an important process to optimizing a 4-Dimensional Schedule (3-D space and time).

I like the fact that every paper I read on a reconfigurable computer operating system says something like "reconfigurable computing operating systems are a rather new area of research." How many times does that get written in the academic world before it can no longer be considered a new area of research?

It's really nifty to think about a "hardware configuration manager" sitting at the very bottom level of an OS. VMware is already in the "hardware virtualization" business. I wonder if anyone there had considered usign FPGAs to accelerate their platform?

molecular computing

I've often suggested that self-assembled molecular electronics would be in the form of reconfigurable arrays. I found this article to back it up.

"We've now discovered molecules that act just like reconfigurable logic bits," says Hewlett-Packard's Kuekes. "We are proposing fairly simple devices that can be literally grown with chemistry. Then all the complexity will be downloaded into configuration bits once the structure is made." Kuekes expects this technology will come to fruition in about ten years, just about the time silicon will peter out. "Reconfigurable logic won't just be a good idea," says Kuekes. "It will be the only way to do computing in the future."

function multiplexing

The CTO of Xilinx came to MIT to check out the 6.111 projects and to give a talk on the future of FPGA. He mentioned most of the stuff I babble about in this blog. He discussed the need for better tools to increase the transparency of targetting FPGAs to open the market up to computer scientists (who outnumber us Electrical Engineers by 100 to 1). He also specifically mentioned dynamic partial reconfiguration and the need for an operating systems to support it.

I asked him a question about function multiplexing (setting up multiple configurations for a LUT and using a global switch to select a configuration). I wanted to know if Xilinx had any plans to deliver chips to support it. He said no. He expressed the opinion that the space used by the additional RAM would be better spent on additional LUTs in which one could implement the multiplexed function. Thus it's probably bettter to just implement the multiplexing in the configware. I'm not sure if this changes my opinion on using dynamic partial reconfiguration with function multiplexing to implement a paging mechanism to swap configurations. I suppose if reconfiguration can be done fast enough it would make sense to implement a set of multiplexed functions and alter them. There's a lot of stuff to consider here.

If the use of an operating system for an FPGA catches on, it is likely that morphware fabrics will be tuned specifically for the OS. Dynamic partial reconfiguration is a relatively new area of exploration so the hardware support for them is still limited. There's only one path for reconfiguration on an FPGA (as in you cannot reconfigure multiple blocks simultaneously). If multiple disjoint processes require reconfiguration it would be nice to do the operations in parallel. We shall see...

I turned on anonymous comments on this blog at the request of someone who emailed me. If there are people reading this who are interested in reconfigurable computing, feel free to get in touch with me! If you're in the valley this summer we could meet up and have some beers or something.

recursive circuit definition

One of the problems with most HDLs is that they do not support recursively defined circuits. It's not too hard to make macros for such things in other languages, but as the circuit size gets too large it becomes impractical to implement. However a mechanism for handling such things would be really useful.

Recursive functional programs map to recursive structural circuits. We want an implementation mechanism for recursively defined circuits that uses continuations at break points to dynamically modify the configware layer. A "dispatch" circuit should also be possibility, depending on a request the dispatch circuit will spawn a new circuit. A lot of the implementation for such a system should follow from the implementation of a concurrent evaluator for a functional language.