Kevin Morris over at FPGA Journal wrote a really good entry about the evolution of FPGA design and how the tools always target the intended market--even if they don't know the underlying execution engine is a reconfigurable array.
So if you want to make a product for the finance dudes, then you're building a spreadsheet--conveniently familiar reconfigurable array. The Accelerator thinks quantitative finance is a bunk field for Accelerated Computing enthusiasts. I say regardless of the underlying economic/ethical question he raises, having an arbitrary market for low-latency computation isn't necessarily bad. If some combination of low latency LAPACK routines lets me print money for my own biochemical endeavors then I'm willing to write them (incidentally, the 18.330 professor who taught me some of those LAPACK routines now works at DE Shaw).
We setup a public SVN to store our spreadsheet tools. See the Catalyst Accelerated Computing Trac page. Anonymous check-in enabled if you want to add a spreadsheet that does something nifty. I'll update this blog when we have releases.
Wednesday, April 09, 2008
Monday, March 31, 2008
Addendum to RhoZeta source
To add to my RhoZeta post from a few weeks back, I thought I'd add an example CellManager. This code demonstrates how to make a Non-Blocking cell manager on a RhoZeta sheet, and how to spawn such a thread for the ActiveSheet in Excel. If you add this to the RhoZeta.py, run the code, and then type "NBCM = NBActiveSheet()" into the PythonWin interactive console you will create a non-blocking style cell manager in the active sheet.
If the CellManager thread craps out (there's a bug when the dictionary changes size in the middle of computation) you can just recreate it by typing "NBCM = NBActiveSheet()" into the console. (start the thread with NBCM.start())
To determine the iteration time, put "=time.clock()" into Cell A1, "=A1" into Cell A2, and "=A1-A2" into cell A3. you can create a simple shift register struction by setting A4 to "=A3" and A5 to "=A4" and so on. This allows you to take the average over a series of tests.
You can also create a counter by initializing B1 to "=0" and then changing it's formula to "=B1 +1" for example.
Non-blocking means all computed assignments are deferred so that all the inputs are read from the previous iteration, as opposed to blocking assignments which read values from the current iteration and assign new values as they are computed. Changing this code to blocking mode iteration is easy to do in terms of number of keystrokes (change eval to exec + a little more massaging, or update valdic as you eval), though I'll leave that as an exercise for you. This Python interpreted modes are slow because of the dynamic eval of strings in Python, compilation is required to accelerated the function calls. JIT compilation to FPGA/GPU/Multicore is what is really required to accelerate spreadsheet iteration... hence a start-up.
#start copying here:
cell.Value = None
elif (cell.Formula[0:1] == "'=") or (cell.Formula[0] == "="):
cell.Value = eval(cell.Formula[1:].lstrip('='),globals(),valdic)
else:
cell.Value = cell.Value
except Exception,e:
cell.Value=e
class NonBlockingCellManager(Timeout):
def __init__(self, Sheet):
Timeout.__init__(target=SheetNonBlockingAssignments, kwargs={'Sh':Sheet})
self.set_run_forever()
def NBActiveSheet():
as = RZ.UISession.app.ActiveSheet
NBCM = NonBlockingCellManager(RZ[as.Parent.Name][as.Name])
return NBCM
#End copy
Another useful change to the FrontendSynchronizer class looks like this:
if xl.ActiveWindow.DisplayFormulas:
setv = RangeMap(Excel.strifnotnone, self.RhoZetaSession.RangeFromTuple(vrtuple).Formula)
else:
setv = RangeMap(Excel.strifnotnone, self.RhoZetaSession.RangeFromTuple(vrtuple).Value)
Press CTRL-` to toggle the DisplayFormulas variable in Excel.
We'll put up source control soon. Feel free to email me at amirh at mit dot edu with questions comments or if you want to help.
If the CellManager thread craps out (there's a bug when the dictionary changes size in the middle of computation) you can just recreate it by typing "NBCM = NBActiveSheet()" into the console. (start the thread with NBCM.start())
To determine the iteration time, put "=time.clock()" into Cell A1, "=A1" into Cell A2, and "=A1-A2" into cell A3. you can create a simple shift register struction by setting A4 to "=A3" and A5 to "=A4" and so on. This allows you to take the average over a series of tests.
You can also create a counter by initializing B1 to "=0" and then changing it's formula to "=B1 +1" for example.
Non-blocking means all computed assignments are deferred so that all the inputs are read from the previous iteration, as opposed to blocking assignments which read values from the current iteration and assign new values as they are computed. Changing this code to blocking mode iteration is easy to do in terms of number of keystrokes (change eval to exec + a little more massaging, or update valdic as you eval), though I'll leave that as an exercise for you. This Python interpreted modes are slow because of the dynamic eval of strings in Python, compilation is required to accelerated the function calls. JIT compilation to FPGA/GPU/Multicore is what is really required to accelerate spreadsheet iteration... hence a start-up.
#start copying here:
def SheetNonBlockingAssignments(Sh):
valdic = {}
for key,value in Sh.Cells.iteritems():
valdic[key]=value.Value
for cell in Sh.Cells.values():
try:
cell.Value = None
elif (cell.Formula[0:1] == "'=") or (cell.Formula[0] == "="):
cell.Value = eval(cell.Formula[1:].lstrip('='),globals(),valdic)
else:
cell.Value = cell.Value
except Exception,e:
cell.Value=e
class NonBlockingCellManager(Timeout):
def __init__(self, Sheet):
Timeout.__init__(target=SheetNonBlockingAssignments, kwargs={'Sh':Sheet})
self.set_run_forever()
def NBActiveSheet():
as = RZ.UISession.app.ActiveSheet
NBCM = NonBlockingCellManager(RZ[as.Parent.Name][as.Name])
return NBCM
#End copy
Another useful change to the FrontendSynchronizer class looks like this:
if xl.ActiveWindow.DisplayFormulas:
setv = RangeMap(Excel.strifnotnone, self.RhoZetaSession.RangeFromTuple(vrtuple).Formula)
else:
setv = RangeMap(Excel.strifnotnone, self.RhoZetaSession.RangeFromTuple(vrtuple).Value)
Press CTRL-` to toggle the DisplayFormulas variable in Excel.
We'll put up source control soon. Feel free to email me at amirh at mit dot edu with questions comments or if you want to help.
Friday, March 28, 2008
Xilinx Favors Clusters to FPGA for Application Acceleration
My last post got 40x my usual traffic. Apparently Python Spreadsheets is a hot topic. It also looks like reconfigurable dataflow networks aren't popular under the moniker of a four letter acronym. When you call it a hardware spreadsheet, a 2-D tiled array of functional blocks is suddenly a whole lot more more accessible.
A few posts back I recounted the tale (and linked to papers that agreed) that the proprietary nature of the FPGA industry impedes reconfigurable computing research with locked-down binary formats and expensive/closed-source (un-study-able) EDA tools. So now let me create a little more controversy. I think it's about time FPGA manufacturers embraced their reconfigurable computing futures. This means that when a major FPGA manufacturer has an EDA problem requiring accelerated computation, they should go with the FPGA approach for accelerating that problem instead of (or at least in addition to) the Cluster or GPU approach. I'm talking about the SmartXplorer utility added to Xilinx ISE 10.1.
Here's my gripe: why is Xilinx promoting clusters instead of FPGA acceleration for it's ISE? Of course if you're an EDA company trying to deliver a product, you want to use tested technology for parallel computing, like a cluster. But it's not like there aren't examples accelerating FPGA Placement on FPGAs. And everybody using ISE has an FPGA already -- it's sitting there attached over USB JTAG waiting for a new bitstream to be placed and routed by my cluster -- but we don't have a cluster.
If nothing more, this sends a signal about Xilinx's stance on whether one should invest in FPGA accelerated computing or a cluster solution (if your problem is sorta similar to the types of problems an FPGA EDA tool might have). Now Altera has to release a GPU accelerated workflow for bragging rights.
Something really needs to be fixed here.
(edit on March 31, props to Acceleware for the GPU accelerated workflows)
A few posts back I recounted the tale (and linked to papers that agreed) that the proprietary nature of the FPGA industry impedes reconfigurable computing research with locked-down binary formats and expensive/closed-source (un-study-able) EDA tools. So now let me create a little more controversy. I think it's about time FPGA manufacturers embraced their reconfigurable computing futures. This means that when a major FPGA manufacturer has an EDA problem requiring accelerated computation, they should go with the FPGA approach for accelerating that problem instead of (or at least in addition to) the Cluster or GPU approach. I'm talking about the SmartXplorer utility added to Xilinx ISE 10.1.
Here's my gripe: why is Xilinx promoting clusters instead of FPGA acceleration for it's ISE? Of course if you're an EDA company trying to deliver a product, you want to use tested technology for parallel computing, like a cluster. But it's not like there aren't examples accelerating FPGA Placement on FPGAs. And everybody using ISE has an FPGA already -- it's sitting there attached over USB JTAG waiting for a new bitstream to be placed and routed by my cluster -- but we don't have a cluster.
If nothing more, this sends a signal about Xilinx's stance on whether one should invest in FPGA accelerated computing or a cluster solution (if your problem is sorta similar to the types of problems an FPGA EDA tool might have). Now Altera has to release a GPU accelerated workflow for bragging rights.
Something really needs to be fixed here.
(edit on March 31, props to Acceleware for the GPU accelerated workflows)
Monday, March 17, 2008
Python Spreadsheets: Like Resolver, Only in Excel and Free
(see http://catalystac.com/trac for latest code source)
Resolver Systems sells a product that does Python with a spreadsheet UI. Resolver uses their own spreadsheet frontend. Here's a demo of how to add Pythonability to Excel. This code is buggy and barely tested and its only a small part of what is an even buggier master's thesis. This demo will show you how to synchronize the visible range in Excel from a running Python session. This allows the Python spreadsheet engine to run independently of Excel allowing me to partition and compile sheet iteration functions onto various co-processors and report the values to the frontend at a lower frequency. I worked on this demo enough to hope that it might work on your machine too.
Grab the code that I pieced together and extract both RhoZeta.py and Excel.py into the same directory. The code is free for you to use: Python is a language that thrives off of open-source sweat. Let me know if you do anything with this (amirh at mit dot edu).
Here's the demo steps with screenshots:
CAUTION: DO NOT RUN THIS WITH OPEN EXCEL WORKBOOKS OR YOU MAY SCREW UP YOUR DATA.
Load RhoZeta.py in PythonWin and click on "Run" and "OK."
After Excel loads you will have an empty workbook. Try typing "=range(0,10)" into A1.
As you might expect from a Python spreadsheet this produces the repr() or the list as a text string in cell A1. Now type "=dir()" in cell A2 to discover the local context.
When we entered the formula in A2, the only assigned cell is A1. If this spreadsheet were recalculating we would want cell A2 to constantly update to inform us which cells are in the local context. Now let's see what the global dictionary looks like:
This produces a dictionary representation in A3 (encased by squiggly {} brackets) . In order to access the members of this dictionary we would like to be able to use the form "=A3[key]" but because Excel doesn't like the square [] brackets we need to precede our formula with an apostrophe. If Excel complains about your perfectly reasonable Python formula, you can precede it with an apostrophe (seriously try without the apostrophe ' and enjoy the message).
OK, so we can reference into a dictionary and fetch a function object. In this case "RangeToAddressArray" is a utility function which takes a textual representation of a range and converts it into a 2-D array of addresses. The point here is that we can store a function in a cell and then apply that function using the cell's address.
We can also bind a cell to an anonymous functions using lambda. Here's how to create the square function:
Now let's go put a value in B8 and apply that square function:
You can also reference attributes in the usual way. In this case the ExcelEvents class has an attribute RZ which points to the RhoZeta spreadsheet engine. (The binding mechanism is a bit awkward because of the way ExcelEvents is passed to the win32com DispatchWithEvents method).
We can actually use the RZ object here to read from the cells:
Here B13 contains the formula '=B11['Book1'].Sheets. This screenshot also demos how the ActiveCell has it's formula overwritten with the internal RhoZeta implementation. The idea was to have editable and draggable formulas, but setting the formulas of a Range doesn't work quite yet. Notice B11 reports "#NAME?" as Excel attempts to execute the formula "=ExcelEvents.RZ" which displays in the formula bar.
So this system doesn't do a lot yet, but hopefully this will give a good foot forward to other people to tinker. The remaining spreadsheet engine from my thesis consists of CellManager threads which compile and run the formulas (using asynchronous, blocking or non-blocking interpretations) and Catalyst threads which walk the spreadsheet graph and perform optimizations. I'll incorporate these elements and eventually this will suck even less.
You can also have fun graphing from Excel into PyOpenGL Kinda like what this guy did, but in PyOpenGL. Here's a tease:
Resolver Systems sells a product that does Python with a spreadsheet UI. Resolver uses their own spreadsheet frontend. Here's a demo of how to add Pythonability to Excel. This code is buggy and barely tested and its only a small part of what is an even buggier master's thesis. This demo will show you how to synchronize the visible range in Excel from a running Python session. This allows the Python spreadsheet engine to run independently of Excel allowing me to partition and compile sheet iteration functions onto various co-processors and report the values to the frontend at a lower frequency. I worked on this demo enough to hope that it might work on your machine too.
Grab the code that I pieced together and extract both RhoZeta.py and Excel.py into the same directory. The code is free for you to use: Python is a language that thrives off of open-source sweat. Let me know if you do anything with this (amirh at mit dot edu).
Here's the demo steps with screenshots:
CAUTION: DO NOT RUN THIS WITH OPEN EXCEL WORKBOOKS OR YOU MAY SCREW UP YOUR DATA.
Load RhoZeta.py in PythonWin and click on "Run" and "OK."
After Excel loads you will have an empty workbook. Try typing "=range(0,10)" into A1.
As you might expect from a Python spreadsheet this produces the repr() or the list as a text string in cell A1. Now type "=dir()" in cell A2 to discover the local context.When we entered the formula in A2, the only assigned cell is A1. If this spreadsheet were recalculating we would want cell A2 to constantly update to inform us which cells are in the local context. Now let's see what the global dictionary looks like:This produces a dictionary representation in A3 (encased by squiggly {} brackets) . In order to access the members of this dictionary we would like to be able to use the form "=A3[key]" but because Excel doesn't like the square [] brackets we need to precede our formula with an apostrophe. If Excel complains about your perfectly reasonable Python formula, you can precede it with an apostrophe (seriously try without the apostrophe ' and enjoy the message).OK, so we can reference into a dictionary and fetch a function object. In this case "RangeToAddressArray" is a utility function which takes a textual representation of a range and converts it into a 2-D array of addresses. The point here is that we can store a function in a cell and then apply that function using the cell's address.We can also bind a cell to an anonymous functions using lambda. Here's how to create the square function:Now let's go put a value in B8 and apply that square function:
You can also reference attributes in the usual way. In this case the ExcelEvents class has an attribute RZ which points to the RhoZeta spreadsheet engine. (The binding mechanism is a bit awkward because of the way ExcelEvents is passed to the win32com DispatchWithEvents method).We can actually use the RZ object here to read from the cells:Here B13 contains the formula '=B11['Book1'].Sheets. This screenshot also demos how the ActiveCell has it's formula overwritten with the internal RhoZeta implementation. The idea was to have editable and draggable formulas, but setting the formulas of a Range doesn't work quite yet. Notice B11 reports "#NAME?" as Excel attempts to execute the formula "=ExcelEvents.RZ" which displays in the formula bar.So this system doesn't do a lot yet, but hopefully this will give a good foot forward to other people to tinker. The remaining spreadsheet engine from my thesis consists of CellManager threads which compile and run the formulas (using asynchronous, blocking or non-blocking interpretations) and Catalyst threads which walk the spreadsheet graph and perform optimizations. I'll incorporate these elements and eventually this will suck even less.
You can also have fun graphing from Excel into PyOpenGL Kinda like what this guy did, but in PyOpenGL. Here's a tease:
Friday, March 07, 2008
New Accelerated Computing Blog
Doug O'Flaherty joins Joe Landman and I in trying to sort out what is going on in accelerated computing in blog form. More synchronized neurons is probably a good thing. His blog title, "Lead, Follow, or..." begs a good question. The first thing to sort out: are we making waves, riding waves or just blowing bubbles? Considering the recent trend of bus-standard openness is his baby, I wonder if he agrees with my take on proprietary standards and the EDA business model miring the FPGA acceleration field (go back two entries).
His first post starts with a bang: "I am not a fan of blogs. In general, they are self indulgent musings in search of an editor." This basically sums up my writing for the past 2 years. Blogging helps the accelerated mind sort: if I didn't blog I wouldn't even know what I was thinking most of the time.
Now that both Joe and I have put a link to his blog, I expect him to make the top of the Google search for "Accelerated Computing" in no time at all :)
His first post starts with a bang: "I am not a fan of blogs. In general, they are self indulgent musings in search of an editor." This basically sums up my writing for the past 2 years. Blogging helps the accelerated mind sort: if I didn't blog I wouldn't even know what I was thinking most of the time.
Now that both Joe and I have put a link to his blog, I expect him to make the top of the Google search for "Accelerated Computing" in no time at all :)
Thursday, March 06, 2008
Excel as a 3-D Graphics Engine
Slashdot has a link to an article by Peter Rakos demonstrating how to use Excel to power a 3-D graphics engine.
He touches upon the paradigm shift associated with the spreadsheet dataflow programming model in comparison to traditional sequential imperative programs.
If you've been following my blog you know that my master's thesis argues that a spreadsheet model supporting various sheet calculation modes (non-blocking, blocking and asynchronous) should replace the von Neumann instruction stream as the primitive model for parallel architectures. It tingles to see someone else discovering the same.
He touches upon the paradigm shift associated with the spreadsheet dataflow programming model in comparison to traditional sequential imperative programs.
If you've been following my blog you know that my master's thesis argues that a spreadsheet model supporting various sheet calculation modes (non-blocking, blocking and asynchronous) should replace the von Neumann instruction stream as the primitive model for parallel architectures. It tingles to see someone else discovering the same.
Wednesday, February 27, 2008
DRC Stirs the Kool-Aid
FPGA Journal recently published an article by Michael R. D'Amour of DRC Computer titled "Reconfigurable Computing for Acceleration in HPC." It's refreshing to see other FPGA computing enthusiasts populating the internet. The article discusses the marketable benefits of FPGA accelerators and the barriers this field has traditionally faced in its attempts to break into the mainstream. Early in his article, he hits the nail on the head:
"While there were many reasons for this lack of early widespread acceptance, one major issue has been a lack of standards surrounding reconfigurable processors and the absence of a standardized system architecture that can effectively employ them."
Standardization, and Open Standardization in particular is the only way a technology can mature from a high margin, low volume market to a low margin, high volume market. We've already seen FPGAs win embedded markets by integrating standard microcontroller architectures. The reason technological maturation requires standards is because the transition requires competition. Standardization provides parameters for competition. Proprietary standards simply erect other barriers to entry (NDAs or reverse engineering). Fortunately there's enough of us who think that competing over a small pie is less fun than making the pie bigger, which is the answer to the skeptics question why AMD would want open bus standards if it allows someone to compete them off their own bus. AMD is growing an eco-system in the process, but since they viably compete in the more standard and bigger x86 market, they really don't have much to fear from FPGAs which are still mired by proprietary programming tools. Still FPGA computing is growing it's niches and since many people have been working on these standardization problems, Michael is somewhat justified in posing this outlook:
"Many of the technological barriers to widespread use of reconfigurable computers have been overcome, and with standards-based reconfigurable interfaces and hardware plus a growing body of standard language compilers to support the technology, reconfigurable computing is poised to break through as a viable solution for a wide range of commercial and HPC applications."
This statement is mostly accurate since it starts with the word "many." Certainly DRC deserves a lot of credit for producing a viable co-processor following AMDs open bus specs. An equivalently accurate statement would go like this: Many of the technological barriers to widespread use of reconfigurable computers are a long way from being overcome, with proprietary hardware interfaces and expensive development environments impeding development of viable solutions for commercial and HPC applications.
Indeed Michael approximates this sentiment in his article while explaining why RC hasn't caught on. The problem is, when do we acknowledge the transition has happened? Is it by popular vote of the bloggers, because my casual observation is that FPGAs are losing to GPUs and Multicores there.
I think it has a lot to do with accessibility of the technology. You actually need people building applications. And right now, it's pretty darn tedious and expensive to build any substantial FPGA design (Check out the project videos of 300+ MIT students who mostly agree). After you do build large designs, its non-trivial to target a new architecture. FPGA acceleration requires FPGA acceleration or at least some semblance of iterative dynamism. I'll know the reconfigurable computing wave is coming when an FPGA is running its own open source tool-chain because that means Xilinx or Altera or somebody will actually be drinking from their own juice-boxes. This is not sarcastic though. Why should I buy reconfigurable computing if Xilinx and Altera don't even buy it yet?
Languages and tools for FPGAs are perhaps getting better for the HPC niche, but this is only a start and I will continue to deny that reconfigurable computing has a standard language until someone shows me a language that supports reconfiguration as a primitive notion. I told someone who works at Bluespec about my variant that allows dynamic elaboration and dynamic reassignment of modules and he wondered how that could be useful since it would take so long to re-target the device after any dynamic changes. The "field programmable" thing is still an inside joke among reconfigurable computing enthusiasts, but as I've said before, marketing reconfigurability is a good way for a computing startup to find no market at all. Everyone at Xilinx knows this because everyone who works there at some point cynically made the connection between reconfigurable computing and Gallium Arsenide. Verification and low-volume embedded are the FPGA markets and they pwnd micro-controllers to take the latter, but will an FPGA driving general purpose computing always be a thing of the future?
Despite the tools and proprietary architectures, we will start to see profitable FPGA computing applications pick up, especially where deterministic latency is a big win-factor or where the speedup potential is several orders of magnitude. But there is a long and bumpy road for FPGAs to break through to a wide range of potential applications. What's really holding back FPGA computing is more than just standards, its the inertia of the EDA industry and its market model.
The economic and perhaps cultural barriers for FPGA co-processors are nearly as complex as the technological barriers. The real, and ironic enemy of FPGA accelerated computing is Xilinx, Altera and the entrenched FPGA EDA industry who are most responsible for the proprietary nature of the current toolset and architectures. These organization are actually somewhat threatened by a disturbance to their high margins from the embedded system and verification markets. Breaking through into computing applications means higher volume of lower cost hardware and similarly cheap and familiar tools that don't require special training. If the cost structure doesn't change then the ROI will rarely be found. Indeed Xilinx and Altera have resisted commoditization of their high-end components and they keep their low-level API's mostly under wraps. Their software is free like free beer, but it isn't Free like freedom yet. If low level FPGA computing research requires an NDA to access the binary formats then an iconoclastic high-school student can't just look it up on the net and hack together a compiler over a rainy weekend in Seattle. Didn't Microsoft just open their binary formats? Maybe they could start a trend?
The FPGA EDA community is going to be shaken by a different market model that doesn't take kindly to expensive proprietary tools. The potential scale of a viable FPGA computing industry could compete out-of-existence many current EDA business models that fail to adapt.
Edit on March 3:
Michael's article originally appeared July 13, 2007 in HPCwire
FCCM '07 had a paper which mentioned how proprietary formats have stifled FPGA computing research
A paper and website about reverse-engineering bitstream formats
There's also a comp.arch.fpga thread from 2000 about "FPGA openness" (Google for it)
"While there were many reasons for this lack of early widespread acceptance, one major issue has been a lack of standards surrounding reconfigurable processors and the absence of a standardized system architecture that can effectively employ them."
Standardization, and Open Standardization in particular is the only way a technology can mature from a high margin, low volume market to a low margin, high volume market. We've already seen FPGAs win embedded markets by integrating standard microcontroller architectures. The reason technological maturation requires standards is because the transition requires competition. Standardization provides parameters for competition. Proprietary standards simply erect other barriers to entry (NDAs or reverse engineering). Fortunately there's enough of us who think that competing over a small pie is less fun than making the pie bigger, which is the answer to the skeptics question why AMD would want open bus standards if it allows someone to compete them off their own bus. AMD is growing an eco-system in the process, but since they viably compete in the more standard and bigger x86 market, they really don't have much to fear from FPGAs which are still mired by proprietary programming tools. Still FPGA computing is growing it's niches and since many people have been working on these standardization problems, Michael is somewhat justified in posing this outlook:
"Many of the technological barriers to widespread use of reconfigurable computers have been overcome, and with standards-based reconfigurable interfaces and hardware plus a growing body of standard language compilers to support the technology, reconfigurable computing is poised to break through as a viable solution for a wide range of commercial and HPC applications."
This statement is mostly accurate since it starts with the word "many." Certainly DRC deserves a lot of credit for producing a viable co-processor following AMDs open bus specs. An equivalently accurate statement would go like this: Many of the technological barriers to widespread use of reconfigurable computers are a long way from being overcome, with proprietary hardware interfaces and expensive development environments impeding development of viable solutions for commercial and HPC applications.
Indeed Michael approximates this sentiment in his article while explaining why RC hasn't caught on. The problem is, when do we acknowledge the transition has happened? Is it by popular vote of the bloggers, because my casual observation is that FPGAs are losing to GPUs and Multicores there.
I think it has a lot to do with accessibility of the technology. You actually need people building applications. And right now, it's pretty darn tedious and expensive to build any substantial FPGA design (Check out the project videos of 300+ MIT students who mostly agree). After you do build large designs, its non-trivial to target a new architecture. FPGA acceleration requires FPGA acceleration or at least some semblance of iterative dynamism. I'll know the reconfigurable computing wave is coming when an FPGA is running its own open source tool-chain because that means Xilinx or Altera or somebody will actually be drinking from their own juice-boxes. This is not sarcastic though. Why should I buy reconfigurable computing if Xilinx and Altera don't even buy it yet?
Languages and tools for FPGAs are perhaps getting better for the HPC niche, but this is only a start and I will continue to deny that reconfigurable computing has a standard language until someone shows me a language that supports reconfiguration as a primitive notion. I told someone who works at Bluespec about my variant that allows dynamic elaboration and dynamic reassignment of modules and he wondered how that could be useful since it would take so long to re-target the device after any dynamic changes. The "field programmable" thing is still an inside joke among reconfigurable computing enthusiasts, but as I've said before, marketing reconfigurability is a good way for a computing startup to find no market at all. Everyone at Xilinx knows this because everyone who works there at some point cynically made the connection between reconfigurable computing and Gallium Arsenide. Verification and low-volume embedded are the FPGA markets and they pwnd micro-controllers to take the latter, but will an FPGA driving general purpose computing always be a thing of the future?
Despite the tools and proprietary architectures, we will start to see profitable FPGA computing applications pick up, especially where deterministic latency is a big win-factor or where the speedup potential is several orders of magnitude. But there is a long and bumpy road for FPGAs to break through to a wide range of potential applications. What's really holding back FPGA computing is more than just standards, its the inertia of the EDA industry and its market model.
The economic and perhaps cultural barriers for FPGA co-processors are nearly as complex as the technological barriers. The real, and ironic enemy of FPGA accelerated computing is Xilinx, Altera and the entrenched FPGA EDA industry who are most responsible for the proprietary nature of the current toolset and architectures. These organization are actually somewhat threatened by a disturbance to their high margins from the embedded system and verification markets. Breaking through into computing applications means higher volume of lower cost hardware and similarly cheap and familiar tools that don't require special training. If the cost structure doesn't change then the ROI will rarely be found. Indeed Xilinx and Altera have resisted commoditization of their high-end components and they keep their low-level API's mostly under wraps. Their software is free like free beer, but it isn't Free like freedom yet. If low level FPGA computing research requires an NDA to access the binary formats then an iconoclastic high-school student can't just look it up on the net and hack together a compiler over a rainy weekend in Seattle. Didn't Microsoft just open their binary formats? Maybe they could start a trend?
The FPGA EDA community is going to be shaken by a different market model that doesn't take kindly to expensive proprietary tools. The potential scale of a viable FPGA computing industry could compete out-of-existence many current EDA business models that fail to adapt.
Edit on March 3:
Michael's article originally appeared July 13, 2007 in HPCwire
FCCM '07 had a paper which mentioned how proprietary formats have stifled FPGA computing research
A paper and website about reverse-engineering bitstream formats
There's also a comp.arch.fpga thread from 2000 about "FPGA openness" (Google for it)
Wednesday, January 16, 2008
Tech Predictions for 2008
Sup. Still building a PDP-11 for Ontario Power Generation. I also have DRC Computer with an FPGA and a webcam doing image recognition and motion tracking. We're recruiting people for Catalyst Accelerated Computing if you want to have some fun.
Here are my Tech Predictions for 2008
1) P2P Live Video Streaming Goes HD. A cheap dongle will connect your HDMI TV to the internet: "vendors of copyrighted material" will rush to this space in 2008 (like Netflix, and Apple TV), but video-phoning and pirates will ultimately be the norm. The Pirate Party will start to make an impact in the Swedish Election but the legal issue about information ownership will be continue to waste paper. We've already been playing with our own P2P streaming model for a while, but similar technology is near to taking over BitTorrent. Combined with the Writer's Strike, this technology will end the old media market model. Arr.
2) Software Defined Radio (SDR) -- Google's efforts to free the 700 MHz spectrum are the beginning of a transition in RF policy. The rest of the spectrum will slowly transition to "best-effort" spectrum sharing protocols (ethernet) with SDR chips allowing software programmable frequency selection and data decoding.
3) Accelerated Computing Moves (closer to) Mainstream. In December of last year, AMD named a VP Accelerated Computing and there's a new video about their initiative from CES. An AMD VP is a signal that startups are going to swarm this market now. FPGA and GPU co-processor integration will still suck well into 2009, but people who have mastered this black-art will be in high demand to retool Wall Street and other HPC niches where GOPs and dollars are strongly correlated.
4) Gestural Control and Motion Tracking. iPhone multitouch will still have that magic effect for a few more years, but now you can do it with a WiiMote. Webcam hand tracking will start to catch on in 2008. We've been having fun with this on our DRC box. Full Body DDR will be a major video-game product in 2008 and play off the Rock Band phenomena to give new meaning to the words: "so you think you can dance?"
5) Social Networking goes Botnet. MySpace sucks. Facebook sucks less. Social Networking is a buzz-word past it's prime. People will realize that a social network and a Botnet are roughly the same, with the computational components generally replaced by protein. Aggregation will pick up and distributed content caching will start to make more sense. We've been experimenting with distributed computation using Javascript. Combined with some photo-sharing/recognizing Amazon Mechanical Turk thing we can use the buzzword Web 3.0 to brand the resulting distributed intelligence. Maybe people won't be so creeped out when they realize they are being datamined by Facebook (and everyone else who wants to datamine social network data).
Here are my Tech Predictions for 2008
1) P2P Live Video Streaming Goes HD. A cheap dongle will connect your HDMI TV to the internet: "vendors of copyrighted material" will rush to this space in 2008 (like Netflix, and Apple TV), but video-phoning and pirates will ultimately be the norm. The Pirate Party will start to make an impact in the Swedish Election but the legal issue about information ownership will be continue to waste paper. We've already been playing with our own P2P streaming model for a while, but similar technology is near to taking over BitTorrent. Combined with the Writer's Strike, this technology will end the old media market model. Arr.
2) Software Defined Radio (SDR) -- Google's efforts to free the 700 MHz spectrum are the beginning of a transition in RF policy. The rest of the spectrum will slowly transition to "best-effort" spectrum sharing protocols (ethernet) with SDR chips allowing software programmable frequency selection and data decoding.
3) Accelerated Computing Moves (closer to) Mainstream. In December of last year, AMD named a VP Accelerated Computing and there's a new video about their initiative from CES. An AMD VP is a signal that startups are going to swarm this market now. FPGA and GPU co-processor integration will still suck well into 2009, but people who have mastered this black-art will be in high demand to retool Wall Street and other HPC niches where GOPs and dollars are strongly correlated.
4) Gestural Control and Motion Tracking. iPhone multitouch will still have that magic effect for a few more years, but now you can do it with a WiiMote. Webcam hand tracking will start to catch on in 2008. We've been having fun with this on our DRC box. Full Body DDR will be a major video-game product in 2008 and play off the Rock Band phenomena to give new meaning to the words: "so you think you can dance?"
5) Social Networking goes Botnet. MySpace sucks. Facebook sucks less. Social Networking is a buzz-word past it's prime. People will realize that a social network and a Botnet are roughly the same, with the computational components generally replaced by protein. Aggregation will pick up and distributed content caching will start to make more sense. We've been experimenting with distributed computation using Javascript. Combined with some photo-sharing/recognizing Amazon Mechanical Turk thing we can use the buzzword Web 3.0 to brand the resulting distributed intelligence. Maybe people won't be so creeped out when they realize they are being datamined by Facebook (and everyone else who wants to datamine social network data).
Monday, October 08, 2007
Mandelbrot Set in Excel
As part of my "anything you can do, I can do in Excel" crusade, I made a spreadsheet to compute the Mandelbrot set (2.5 MB file). This takes roughly 5 seconds per iteration on a single-core Pentium 4 at 2.6 GHz. Excel also seems to consume 128 MB of memory to compute the 400 x 350 x 2 sheets of cells (compare to 28 MB just to run Excel). The slowness and memory overhead (probably related) of this operation in Excel points to some serious design flaws in the underlying spreadsheet calculation system. Considering the spreadsheet file is around 2.5 MB, I can't see why the entire thing would require more than say 5 MB (one to store the current iteration and one to store the next in order to preserve atomicity). Since Excel's iteration is blocking assignments in reading order, the actual iteration could require no more memory than the entire 2.5 MB sheet if atomicity of the iteration operation is not a concern. Since this spreadsheet is embarrassingly parallel and requires vastly more floating point resources than can fit on an FPGA, it makes for a good benchmark of a resource sharing compiler (aka a serializing compiler).
Time for pictures. These are produced by Excel's conditional cell coloring. The images link to bigger PNG versions.
After 1 iteration (minx = -2, maxy = 1, dx = .01, dy = .01)
After 2 iterations
Several iterations later, it starts to resemble a Mandelbrot set.
Several more iterations and some cells start to diverge.
Everyone's favorite fractal: the Mandelbrot Set!
Zooming in on a particular section and iterating a bunch.
Time for pictures. These are produced by Excel's conditional cell coloring. The images link to bigger PNG versions.
After 1 iteration (minx = -2, maxy = 1, dx = .01, dy = .01)
After 2 iterations
Several iterations later, it starts to resemble a Mandelbrot set.
Several more iterations and some cells start to diverge.
Everyone's favorite fractal: the Mandelbrot Set!
Zooming in on a particular section and iterating a bunch.
Saturday, September 15, 2007
Datacenter Power Management: Subverting the Dominant Paradigm
The purpose of this entry is to dispell the meme that increasing server utilization is a viable long term approach to power management. The dominant paradigm is that virtualization technology will allow you to increase your server utilization and therefore allow you to improve total performance per watt. White papers from AMD and Intel both discuss consolidation as a means to data center power reduction and PG&E incetivizes the use of virtualization technology. While encouraging managed virtual machines for power consumption is a good model, increasing utilization is not a viable long-term model for optimizing GOps/Watt.
The point I would like to make is that in order to decrease power consumption, it may be necessary to buy more chips and distribute the load better. As a rule-of-thumb, in traditional CMOS hardware design, power consumption is cubically dependent on clock frequency. In ultra-low-power systems employing subthreshold, adiabatic and asynchronous logic, this speed-power relationship has an even higher order.
An analogy that makes sense to everyone is that when you coast your car, you achieve optimal miles-per-gallon, but you can't achieve any meaningful speed. Applying a little gas results in an optimal moving speed, but once you apply too much gas to maintain a high speed, your fuel-efficiency drops again.
As a reference point, you can buy microcontrollers at 1 MHz consuming ~400 micro-Watts. Architectures with finer granularity of power and frequency management allow you to distribute 1000 1-MHz virtual machines onto 1000 1-MHz cores instead of consolidating them to run on a single 1-GHz core. By the cubic rule of thumb, each of the 1000 1-MHz cores consumes a billionth of the power, resulting in one millionth total power consumption. Static currents and fixed overhead causes this cubic model to break down at some "power-optimal clock speed."
Dynamic voltage and frequency scaling in multicore arrays may allow each core to have its own power/clock domain in a globally asynchronous model. To optimize for static currents, using dynamic threshold scaling (modulating the body bias voltage of the chip) along with dynamic voltage scaling seems to be a viable technique. Here's a spreadsheet model for leakage current in a transistor varying Temparature, power and threshold voltage across a reasonable range. At lower frequencies, higher threshold voltages can be used to offset leakage power consumption. Such dynamic leakage reduction cannot be achieve using only multi-threshold CMOS (using high-threshold power-enable transistors). Since this static leakage current factor is increasingly a dominant factor in chip power consumption as channel lengths shrink to 45 nm and below, using threshold scaling with power-frequency scaling results in a higher that cubically ordered relationship between power consumption and clock speed.
Instead of increasing the utilization of a single chip, we can fundamentally decrease our need for gigahertz frequency computation and thus decrease power consumption by increasing the parallelism of our systems. Invoking Seymour Cray: while 1024 chickens may not plow a field as quickly as 2 Strong Oxen, they may plow it fast enough and for a lot less chicken-feed.
The point I would like to make is that in order to decrease power consumption, it may be necessary to buy more chips and distribute the load better. As a rule-of-thumb, in traditional CMOS hardware design, power consumption is cubically dependent on clock frequency. In ultra-low-power systems employing subthreshold, adiabatic and asynchronous logic, this speed-power relationship has an even higher order.
An analogy that makes sense to everyone is that when you coast your car, you achieve optimal miles-per-gallon, but you can't achieve any meaningful speed. Applying a little gas results in an optimal moving speed, but once you apply too much gas to maintain a high speed, your fuel-efficiency drops again.
As a reference point, you can buy microcontrollers at 1 MHz consuming ~400 micro-Watts. Architectures with finer granularity of power and frequency management allow you to distribute 1000 1-MHz virtual machines onto 1000 1-MHz cores instead of consolidating them to run on a single 1-GHz core. By the cubic rule of thumb, each of the 1000 1-MHz cores consumes a billionth of the power, resulting in one millionth total power consumption. Static currents and fixed overhead causes this cubic model to break down at some "power-optimal clock speed."
Dynamic voltage and frequency scaling in multicore arrays may allow each core to have its own power/clock domain in a globally asynchronous model. To optimize for static currents, using dynamic threshold scaling (modulating the body bias voltage of the chip) along with dynamic voltage scaling seems to be a viable technique. Here's a spreadsheet model for leakage current in a transistor varying Temparature, power and threshold voltage across a reasonable range. At lower frequencies, higher threshold voltages can be used to offset leakage power consumption. Such dynamic leakage reduction cannot be achieve using only multi-threshold CMOS (using high-threshold power-enable transistors). Since this static leakage current factor is increasingly a dominant factor in chip power consumption as channel lengths shrink to 45 nm and below, using threshold scaling with power-frequency scaling results in a higher that cubically ordered relationship between power consumption and clock speed.
Instead of increasing the utilization of a single chip, we can fundamentally decrease our need for gigahertz frequency computation and thus decrease power consumption by increasing the parallelism of our systems. Invoking Seymour Cray: while 1024 chickens may not plow a field as quickly as 2 Strong Oxen, they may plow it fast enough and for a lot less chicken-feed.
Monday, September 10, 2007
Evolving Beyond One-Dimensional Programming; Why Foo-C is not a Parallel Programming Environment
In my last blog entry, I introduced the spreadsheet parallel programming model that I will be evangelizing for the next several years. The goal of this entry is to contrast the spreadsheet programming model with existing attempts at C-like parallel programming environments. I argue that one-dimensional von Neumann languages are insufficient for expressing the objectives of a parallel program and that any "parallel programming" extension to C is a temporary solution to a bigger problem.
A programming objective is most generally one of two things: a functional procedure or a state modifying atomic action. In hardware, these notions respectively correspond to resolving a combinatorial circuit and latching a register. In software descriptions these correspond to evaluating a pure-function and assigning the result to the left-hand-side variable. Often these concepts are not separated in the mind of the sequential imperative programmer; each piece of code is thought of as a sequence of instructions that is executed as it is read. This programming model matches the hardware most software engineers have used for the past 60 years and so it is the dominant paradigm.
In the sequential school of thought, functions are just subroutines which return a value. Since most languages do not strictly isolate state assignment from functional value determination, the order in which functional computations and assignments are performed matters to the correctness of the program. Thus a program is generally some contortion within a language to achieve either a functional or atomic-action objective. In this sense, the programmer is devising not a solution to a problem, but an expression of the solution in some language.
Software programmers rarely create code the way we think about the problem, but rather we solve the problem in the manner that the language provides. Computer programming has predominantly been the engineering practice of projecting combinatorial functions or atomic actions into a one-dimensional execution order. The work of a parallelizing compiler may be considered a process of "re-functionalizing" the one-dimensional projection produced by the programmer. Unfortunately, sequential imperative control flow confounds a parallelizing compiler and introduces a bottleneck which cannot easily be anti-projected from one-dimension to many. Speculation seems to be the mode for improving the concurrency of our code, though parallelism is not achieved through brute-force speculation alone since speculation is an inefficient parallelization primitive when we explore too many unlikely paths.
Herein lies the key difference between software and reconfigurable hardware programming. Software is a control-centric model and reconfigurable computing is a data-centric model. Any sort of programmatic control flow in reconfigurable hardware must be explicitly managed by state-machines, whereas control flow in an instruction stream is implicit (next instruction) or managed with branching. The C programmer mangles what could have been a multiplexor into control flow case statements. An if statement only evaluates one path after the predicate resolves while a multiplexer resolves all inputs simultaneously while the predicate is being determined. Expressing this sort of parallelism is impossible in C since simultaneity is not a component of the language.
Ultimately the problem of a parallelizing compiler resolving C-like control flow is this: when do we want our conditional statements to be an "if" and when do we want them to be a muliplexer? By writing code in a von Neumann language we are forcing one-dimensionality in our code and explicitly sequentializing what could otherwise be a parallel expression.
A programming objective is most generally one of two things: a functional procedure or a state modifying atomic action. In hardware, these notions respectively correspond to resolving a combinatorial circuit and latching a register. In software descriptions these correspond to evaluating a pure-function and assigning the result to the left-hand-side variable. Often these concepts are not separated in the mind of the sequential imperative programmer; each piece of code is thought of as a sequence of instructions that is executed as it is read. This programming model matches the hardware most software engineers have used for the past 60 years and so it is the dominant paradigm.
In the sequential school of thought, functions are just subroutines which return a value. Since most languages do not strictly isolate state assignment from functional value determination, the order in which functional computations and assignments are performed matters to the correctness of the program. Thus a program is generally some contortion within a language to achieve either a functional or atomic-action objective. In this sense, the programmer is devising not a solution to a problem, but an expression of the solution in some language.
Software programmers rarely create code the way we think about the problem, but rather we solve the problem in the manner that the language provides. Computer programming has predominantly been the engineering practice of projecting combinatorial functions or atomic actions into a one-dimensional execution order. The work of a parallelizing compiler may be considered a process of "re-functionalizing" the one-dimensional projection produced by the programmer. Unfortunately, sequential imperative control flow confounds a parallelizing compiler and introduces a bottleneck which cannot easily be anti-projected from one-dimension to many. Speculation seems to be the mode for improving the concurrency of our code, though parallelism is not achieved through brute-force speculation alone since speculation is an inefficient parallelization primitive when we explore too many unlikely paths.
Herein lies the key difference between software and reconfigurable hardware programming. Software is a control-centric model and reconfigurable computing is a data-centric model. Any sort of programmatic control flow in reconfigurable hardware must be explicitly managed by state-machines, whereas control flow in an instruction stream is implicit (next instruction) or managed with branching. The C programmer mangles what could have been a multiplexor into control flow case statements. An if statement only evaluates one path after the predicate resolves while a multiplexer resolves all inputs simultaneously while the predicate is being determined. Expressing this sort of parallelism is impossible in C since simultaneity is not a component of the language.
Ultimately the problem of a parallelizing compiler resolving C-like control flow is this: when do we want our conditional statements to be an "if" and when do we want them to be a muliplexer? By writing code in a von Neumann language we are forcing one-dimensionality in our code and explicitly sequentializing what could otherwise be a parallel expression.
Wednesday, September 05, 2007
A Replacement for the von Neumann Model
"What is a von Neumann computer? When von Neumann and others conceived it over thirty years ago, it was an elegant, practical, and unifying idea that simplified a number of engineering and programming problems that existed then. Although the conditions that produced its architecture have changed radically, we nevertheless still identify the notion of "computer" with this thirty year old concept."
John Backus, “Can Programming Be Liberated from the von Neumann Style?” Turing Award Lecture, 1977
Yesterday I submitted my Master's thesis to MIT's department of Electrical Engineering and Computer Science. In my thesis I present my answer to the problem: how do we program parallel architectures?
My answer is to use a spreadsheet as a replacement for the von Neumann model since modern hardware more accurately resembles an array of processing units than a single instruction stream executer. Since spreadsheets are already a well-established dataflow development paradigm, tools already exist to make spreadsheet specification extremely rapid and straightforward. Unfortunately existing spreadsheet applications aren't designed with the intent of being complete programming languages and they often treat circular reference like an error--though you can enable manual iteration in Excel (try making a counter, IIR filter and a RISC CPU in Excel as an exercise--F9 to iterate). To make the spreadsheets a better parallel programming tool I added multiple interpreter modes (asynchronous, blocking and non-blocking assignments like Verilog), behavioral abstraction, guarded atomic action macros and compilation to FPGA, GPU and Multicore.
My thesis title is "Compiling and Optimizing Spreadsheets for FPGA and Multicore Execution"
Here is the abstract:
A major barrier to developing systems on multicore and FPGA chips is an easy-to-use development environment. This thesis presents the RhoZeta spreadsheet compiler and Catalyst optimization system for programming multiprocessors and FPGAs. Any spreadsheet frontend may be extended to work with RhoZeta’s multiple interpreters and behavioral abstraction mechanisms. RhoZeta synchronizes a variety of cell interpreters acting on a global memory space. RhoZeta can also compile a group of cells to multithreaded C or Verilog. The result is an easy-to-use interface for programming multicore microprocessors and FPGAs. A spreadsheet environment presents parallelism and locality issues of modern hardware directly to the user and allows for a simple global memory synchronization model. Catalyst is a spreadsheet graph rewriting system based on performing behaviorally invariant guarded atomic actions while a system is being interpreted by RhoZeta. A number of optimization macros were developed to perform speculation, resource sharing and propagation of static assignments through a circuit. Parallelization of a 64-bit serial leading-zero-counter is demonstrated with Catalyst. Fault tolerance macros were also developed in Catalyst to protect against dynamic faults and to offset costs associated with testing semiconductors for static defects. A model for partitioning, placing and profiling spreadsheet execution in a heterogeneous hardware environment is also discussed. The RhoZeta system has been used to design several multithreaded and FPGA applications including a RISC emulator and a MIDI controlled modular synthesizer.
John Backus, “Can Programming Be Liberated from the von Neumann Style?” Turing Award Lecture, 1977
Yesterday I submitted my Master's thesis to MIT's department of Electrical Engineering and Computer Science. In my thesis I present my answer to the problem: how do we program parallel architectures?
My answer is to use a spreadsheet as a replacement for the von Neumann model since modern hardware more accurately resembles an array of processing units than a single instruction stream executer. Since spreadsheets are already a well-established dataflow development paradigm, tools already exist to make spreadsheet specification extremely rapid and straightforward. Unfortunately existing spreadsheet applications aren't designed with the intent of being complete programming languages and they often treat circular reference like an error--though you can enable manual iteration in Excel (try making a counter, IIR filter and a RISC CPU in Excel as an exercise--F9 to iterate). To make the spreadsheets a better parallel programming tool I added multiple interpreter modes (asynchronous, blocking and non-blocking assignments like Verilog), behavioral abstraction, guarded atomic action macros and compilation to FPGA, GPU and Multicore.
My thesis title is "Compiling and Optimizing Spreadsheets for FPGA and Multicore Execution"
Here is the abstract:
A major barrier to developing systems on multicore and FPGA chips is an easy-to-use development environment. This thesis presents the RhoZeta spreadsheet compiler and Catalyst optimization system for programming multiprocessors and FPGAs. Any spreadsheet frontend may be extended to work with RhoZeta’s multiple interpreters and behavioral abstraction mechanisms. RhoZeta synchronizes a variety of cell interpreters acting on a global memory space. RhoZeta can also compile a group of cells to multithreaded C or Verilog. The result is an easy-to-use interface for programming multicore microprocessors and FPGAs. A spreadsheet environment presents parallelism and locality issues of modern hardware directly to the user and allows for a simple global memory synchronization model. Catalyst is a spreadsheet graph rewriting system based on performing behaviorally invariant guarded atomic actions while a system is being interpreted by RhoZeta. A number of optimization macros were developed to perform speculation, resource sharing and propagation of static assignments through a circuit. Parallelization of a 64-bit serial leading-zero-counter is demonstrated with Catalyst. Fault tolerance macros were also developed in Catalyst to protect against dynamic faults and to offset costs associated with testing semiconductors for static defects. A model for partitioning, placing and profiling spreadsheet execution in a heterogeneous hardware environment is also discussed. The RhoZeta system has been used to design several multithreaded and FPGA applications including a RISC emulator and a MIDI controlled modular synthesizer.
Wednesday, August 08, 2007
Theres probably a few hundred of us
I haven't updated this blog in a while. I've been traveling and writing a thesis full of monadic deliciousness and behavioral invariant transformations--coming soon. I started a job last month making a PDP-11 emulator at Quickware.
There's probably a few hundred of us who are watching the accelerated computing meme spread. It is catching on, there's probably a few dozen of us ready to put our mouth where the money is when wall street catches on too--email me by the way (my name at where i work).
Just wanted to point out that big supercomputers are used to analyze carbon dioxide emissions due to the ever increasing amount of energy required to power our big super computers.
And programming environments always seem to suck unless you build it yourself. Thank Gerry for Scheme though.
There's probably a few hundred of us who are watching the accelerated computing meme spread. It is catching on, there's probably a few dozen of us ready to put our mouth where the money is when wall street catches on too--email me by the way (my name at where i work).
Just wanted to point out that big supercomputers are used to analyze carbon dioxide emissions due to the ever increasing amount of energy required to power our big super computers.
And programming environments always seem to suck unless you build it yourself. Thank Gerry for Scheme though.
Wednesday, April 25, 2007
AMD White Paper
Joe Landman over at scalability.org has written up a white paper for AMD on accelerated computing technology.
Friday, January 26, 2007
Recognition via Synthesis and Replication
Many recognition systems work by applying transformations on input data to map a feature space to a more "friendly" feature space. The transformations are generally destructive, non-reversible filters (ie edge detection or color removal in video, frequency selective filtering in audio). This implies a destruction of information in the signal path: by filtering data we reducing the variance of our state-space to focus on "interesting" features. After filtering the data, the result is a more "familiar" feature space on which to perform reductive analysis.
In order to recognize speech we may eliminate all uninteresting frequencies by taking local maxima above a certain threshold. By looking at the relative amplitudes of interesting frequencies, we can identify a set of conditions that categorize each of the sounds into phonemes (record yourself saying ooh and ahh and look at an FFT and you'll get an idea of what a computer might want to look for). The conditions for categorizing an input stram is often trained against a known data set.
Today at the HKN Student Project expo, two 6.111 projects showed how an FPGA can be used to identify a person's hands (juggling simulation) and colored patches and gloves (full body DDR). These systems recognize where a color is by filtering color from video data and identifying the center of mass of each color. Such filter and reduce (alludes to MapReduce of Google) recognition systems will be an important part of artificially intelligent system. Real-world solutions while sharing this common programming model, still require a significant amount of energy to program and train resulting in highly domain specific implementations.
Perhaps it would be useful to produce a general set of filters and reductive analyses. The system, guided by a programmer would assemble the filters and reductions to produce an output from an input stream: where are the hands in this image stream, what is the word in this audio stream. I realized that training such a system, would be simpler, but there is still the problem of calibrating a paramater space for the filters: which frequencies are interesting, what size of red-blob in a filtered image qualifies as a hand? How do we handle arbitrary training sets?
This problem is closely related to speech synthesis: what parameters for tone generators and filters are necessary to model a voice? It struck me that perhaps the reason we recognize and understand speech is because we can mimic the words and the intentions expressed. We recognize and understand when someone says "I am happy," because we can both produce the expression and sympathize with the emotion. Recognition is probably the lower hanging fruit than understanding.
The K-lines activated in person A when a person B says "happy" is instrinsically connected to the K-lines person A uses to control his voice. A computer could perform recognition by modulating the controls of a synthesizer to minimize the difference between the heard tone and the synthesized tone. This could apply to a video recognition system as well: attempt to render a scene matching what it sees. To find a hand, it renders a parametric model of a hand until we realize where what parameters for the hand to minimize the error between the rendered image and the seen image to a point where we are confident we have located the hand properly.
Since I'm a synth junkie, I think of a computer controlling the knobs on a synth to mimic a sound. By examining the gestures used to produce the sound, the synthesizer would recognize the world hello by realizing it is saying "hello" when it attempts to mimic the input. By translating an input space to a control-space we can produce a set of meaningful symbols on which to perform analysis. Useful control parameters are orthogonal/independent: if we modulate them in isolation we could find a parametric minima that is a component of the global minima. It is also nice if our parameters themselves do not have local minima in order to simplify minimization.
We don't always get that kind of niceness... perhaps we can take advantage of the continuity of trajectories in the physical world to imply only incremental modulation is required to control and maintain accurate replication synthesis.
In order to recognize speech we may eliminate all uninteresting frequencies by taking local maxima above a certain threshold. By looking at the relative amplitudes of interesting frequencies, we can identify a set of conditions that categorize each of the sounds into phonemes (record yourself saying ooh and ahh and look at an FFT and you'll get an idea of what a computer might want to look for). The conditions for categorizing an input stram is often trained against a known data set.
Today at the HKN Student Project expo, two 6.111 projects showed how an FPGA can be used to identify a person's hands (juggling simulation) and colored patches and gloves (full body DDR). These systems recognize where a color is by filtering color from video data and identifying the center of mass of each color. Such filter and reduce (alludes to MapReduce of Google) recognition systems will be an important part of artificially intelligent system. Real-world solutions while sharing this common programming model, still require a significant amount of energy to program and train resulting in highly domain specific implementations.
Perhaps it would be useful to produce a general set of filters and reductive analyses. The system, guided by a programmer would assemble the filters and reductions to produce an output from an input stream: where are the hands in this image stream, what is the word in this audio stream. I realized that training such a system, would be simpler, but there is still the problem of calibrating a paramater space for the filters: which frequencies are interesting, what size of red-blob in a filtered image qualifies as a hand? How do we handle arbitrary training sets?
This problem is closely related to speech synthesis: what parameters for tone generators and filters are necessary to model a voice? It struck me that perhaps the reason we recognize and understand speech is because we can mimic the words and the intentions expressed. We recognize and understand when someone says "I am happy," because we can both produce the expression and sympathize with the emotion. Recognition is probably the lower hanging fruit than understanding.
The K-lines activated in person A when a person B says "happy" is instrinsically connected to the K-lines person A uses to control his voice. A computer could perform recognition by modulating the controls of a synthesizer to minimize the difference between the heard tone and the synthesized tone. This could apply to a video recognition system as well: attempt to render a scene matching what it sees. To find a hand, it renders a parametric model of a hand until we realize where what parameters for the hand to minimize the error between the rendered image and the seen image to a point where we are confident we have located the hand properly.
Since I'm a synth junkie, I think of a computer controlling the knobs on a synth to mimic a sound. By examining the gestures used to produce the sound, the synthesizer would recognize the world hello by realizing it is saying "hello" when it attempts to mimic the input. By translating an input space to a control-space we can produce a set of meaningful symbols on which to perform analysis. Useful control parameters are orthogonal/independent: if we modulate them in isolation we could find a parametric minima that is a component of the global minima. It is also nice if our parameters themselves do not have local minima in order to simplify minimization.
We don't always get that kind of niceness... perhaps we can take advantage of the continuity of trajectories in the physical world to imply only incremental modulation is required to control and maintain accurate replication synthesis.
Tuesday, December 26, 2006
An Interpreted Hardware Description Language
Last semester, some of my classmates and I worked on extensions to Bluespec for Prof. Arvind's class on multithreaded parallelism and compilers. Bluespec's site probably has an overview of the languages ideas, but I'll sum them up here. Bluespec consists of modules which contain registers, rules and methods. A register is a mutable state container. A rule is a guarded atomic action. A guard is a predicate procedure (evalutes to true or false) which determines if the atomic action may be performed. An atomic action is a set of non-blocking assignments and/or method calls that occur instantaneously and completely (all or nothing and with no interuption). A method is similarly a guarded atomic action, however it may accept arguments when it is invoked and it may return a value. If a method call within an atomic action (of a rule or method) has a guard that evaluates to false then the entire atomic action may not be performed.
Methods make up the interface to a module, and may be externally invoked. For example, a module may call any of it's submodules methods within an atomic action. Rules, on the other hand, are entirely internal to the module. Rules may be executed when their guards are true, but there is no imperative within the language to force a particular rule to execute when it's guard is true. Here is an example of a GCD coded in Bluespec.
Bluespec works well as an HDL because the guarded atomic action notion is an exceptionally powerful way to think about designing systems. For starters, the language has no concept of time and is implicitly asynchronous (though I presume all physical implementations are synchronous). Rule based system specification is nice because it provide a clean constructive approach to solving a problem: add rules which transform the system state closer to a terminal state until all possible non-terminal states are accounted for. The other nicety of specifying what the system may do as opposed to what it must do is that it allows for many possible automated optimization strategies in the rule-execution system to minimize system costs (power, area, time). This is a rich area of study and will probably produce many graduate theses ;-)
Our project was focused on sequentializing rules in Bluespec to minimize the amount of hardware required to implement a system (at a tradeoff to speed). For example, the single rule: A <= B + C; B <= D + E; could be split into two rules so that only one adder would be required. This computationally invariant transformation was done with valid Bluespec code as the source and target.
The second aspect of our project was to explore how we could create an interpreted Bluespec-like scripting language. The deficiencies we saw in the Bluespec language are not related to it's functionality as an HDL, but are rather deficiencies common to hardware description in general. In general, HDL types are static and strict, meaning a module or a register are bound to a type at the time they are defined. Some HDLs do have polymorphic type systems (particularly those based on Haskell such as Bluespec). Also, there is no Hardware Description Language with methods that allow dynamic creation of new modules, rules or methods. Dynamic elaboration is desireable in the context of reconfigurable arrays. The language we created for the class was called BlueScheme, which inherited the dynamic typing and first-class procedures from the Scheme language, and guarded atomic actions from Bluespec. The result is a language which supports untyped registers, methods and modules and dynamic modification of modules, methods and rules as an atomic action.
I've independently continued working on this BlueScheme language since after the class has finished. The rest of this document is a specification of how it is designed. A module consists of three hashtables for child-modules, rules and methods. Rules have a guard procedure and an atomic action with no parameters that may not return a value. Methods have a guard procedure and an atomic action which may accept arguments and return a value. Child-modules are the modules whose methods may be called from within a modules atomic action (note that every module is it's own child and is refered to as "me"). I suppose "child" a bit of a misnomer, since multiple modules may share a child module (multiple different modules may use the same GCD).
Rules or methods may be attempted and may succeed or fail. The source of an attempt may be a module which independently attempts a rule or the user who may request a method of a module. If a module attempts a rule or a method is externally invoked and the guard returns false then the failure is propagated to the source, otherwise if the guard succeeds the atomic action will execute. If the atomic action fails, then again the failure signal will propagate to the source. If an attempted atomic action succeeds then it returns a committable action. A commitable action is a thunk (procedure with no arguments) which consists of a set of assignments where the value to be assigned are non-reducible expressions (ie numbers, symbols, lists, strings, modules, methods, rules etc.). If a method Foo returns a commitable action within method Bar's atomic action, Foo's commitable action will be propagated together with the result of Bar. If all attempted actions return to the source without failure, then the source will commit all of the commitable actions by executing the thunk.
Since I have enabled self-modifying modules, I've eliminated registers from the language semantics, and replaced them with modules that support set and get methods (calling set modifies the returned value of the get method). This allows me to add rules to registers that have a random guard and flip the register value or make it disfunctional in order to mimic defective or faulty systems (useful for designing for fault/defect tolerance).
Currently I have only implemented a round-robin rule execution system which attempts rules in a round robin fashion. There is a lot more work that could be done on this end...
The language currently uses Scheme syntax, though we wrote a Bluespec parser and printer for our project and a design that does not contain any dynamic parts could already be converted into valid Bluespec and compiled to C or Verilog. I am also interested in seeing how to use this as a runtime language for a dynamically reconfigurable FPGA. One realization would treat the language as an extension of a file system. In this view we treat modules as "directories," treat rules as running processes scoped within a directory and treat methods as executables. When a module needs acceleration it's directory structure could be moved into the FPGA. Presumably it should still be able to interface with modules that are implemented in sequentially executing CPUs.
In order to transform a module structure into an FPGA structure, we need to type-constrain our modules and methods and map all functional expressions to the FPGA primitives (LUTs, adders). I have implemented a transformation which creates submodules for each functional expression: a <= b + c; becomes a <= adder.add(b,c). I've been looking to Lava to get from here into the FPGA.
We can apply computationally invariant transformations to the module structure to optimize for various cost metrics (see my previous entry on using an economic model as an optimization strategy). Module flattening takes an entire sub-directory structure and flattens it into a single directory. Rule merging takes two disjoint processes and combines them (increasing speed and resource consumption). Rule sequentialization split rules up to conserve resources. Place and route optimizations should also be done, moving modules around within the FPGA to optimize for speed, power and area.
I will put it all online as soon as I write better documentation and work out some demos. If you're interested in seeing the GCD demo please contact me! The most immediate next step I'd like to take is to compile a streaming language into this world of guarded atomic actions.
Methods make up the interface to a module, and may be externally invoked. For example, a module may call any of it's submodules methods within an atomic action. Rules, on the other hand, are entirely internal to the module. Rules may be executed when their guards are true, but there is no imperative within the language to force a particular rule to execute when it's guard is true. Here is an example of a GCD coded in Bluespec.
Bluespec works well as an HDL because the guarded atomic action notion is an exceptionally powerful way to think about designing systems. For starters, the language has no concept of time and is implicitly asynchronous (though I presume all physical implementations are synchronous). Rule based system specification is nice because it provide a clean constructive approach to solving a problem: add rules which transform the system state closer to a terminal state until all possible non-terminal states are accounted for. The other nicety of specifying what the system may do as opposed to what it must do is that it allows for many possible automated optimization strategies in the rule-execution system to minimize system costs (power, area, time). This is a rich area of study and will probably produce many graduate theses ;-)
Our project was focused on sequentializing rules in Bluespec to minimize the amount of hardware required to implement a system (at a tradeoff to speed). For example, the single rule: A <= B + C; B <= D + E; could be split into two rules so that only one adder would be required. This computationally invariant transformation was done with valid Bluespec code as the source and target.
The second aspect of our project was to explore how we could create an interpreted Bluespec-like scripting language. The deficiencies we saw in the Bluespec language are not related to it's functionality as an HDL, but are rather deficiencies common to hardware description in general. In general, HDL types are static and strict, meaning a module or a register are bound to a type at the time they are defined. Some HDLs do have polymorphic type systems (particularly those based on Haskell such as Bluespec). Also, there is no Hardware Description Language with methods that allow dynamic creation of new modules, rules or methods. Dynamic elaboration is desireable in the context of reconfigurable arrays. The language we created for the class was called BlueScheme, which inherited the dynamic typing and first-class procedures from the Scheme language, and guarded atomic actions from Bluespec. The result is a language which supports untyped registers, methods and modules and dynamic modification of modules, methods and rules as an atomic action.
I've independently continued working on this BlueScheme language since after the class has finished. The rest of this document is a specification of how it is designed. A module consists of three hashtables for child-modules, rules and methods. Rules have a guard procedure and an atomic action with no parameters that may not return a value. Methods have a guard procedure and an atomic action which may accept arguments and return a value. Child-modules are the modules whose methods may be called from within a modules atomic action (note that every module is it's own child and is refered to as "me"). I suppose "child" a bit of a misnomer, since multiple modules may share a child module (multiple different modules may use the same GCD).
Rules or methods may be attempted and may succeed or fail. The source of an attempt may be a module which independently attempts a rule or the user who may request a method of a module. If a module attempts a rule or a method is externally invoked and the guard returns false then the failure is propagated to the source, otherwise if the guard succeeds the atomic action will execute. If the atomic action fails, then again the failure signal will propagate to the source. If an attempted atomic action succeeds then it returns a committable action. A commitable action is a thunk (procedure with no arguments) which consists of a set of assignments where the value to be assigned are non-reducible expressions (ie numbers, symbols, lists, strings, modules, methods, rules etc.). If a method Foo returns a commitable action within method Bar's atomic action, Foo's commitable action will be propagated together with the result of Bar. If all attempted actions return to the source without failure, then the source will commit all of the commitable actions by executing the thunk.
Since I have enabled self-modifying modules, I've eliminated registers from the language semantics, and replaced them with modules that support set and get methods (calling set modifies the returned value of the get method). This allows me to add rules to registers that have a random guard and flip the register value or make it disfunctional in order to mimic defective or faulty systems (useful for designing for fault/defect tolerance).
Currently I have only implemented a round-robin rule execution system which attempts rules in a round robin fashion. There is a lot more work that could be done on this end...
The language currently uses Scheme syntax, though we wrote a Bluespec parser and printer for our project and a design that does not contain any dynamic parts could already be converted into valid Bluespec and compiled to C or Verilog. I am also interested in seeing how to use this as a runtime language for a dynamically reconfigurable FPGA. One realization would treat the language as an extension of a file system. In this view we treat modules as "directories," treat rules as running processes scoped within a directory and treat methods as executables. When a module needs acceleration it's directory structure could be moved into the FPGA. Presumably it should still be able to interface with modules that are implemented in sequentially executing CPUs.
In order to transform a module structure into an FPGA structure, we need to type-constrain our modules and methods and map all functional expressions to the FPGA primitives (LUTs, adders). I have implemented a transformation which creates submodules for each functional expression: a <= b + c; becomes a <= adder.add(b,c). I've been looking to Lava to get from here into the FPGA.
We can apply computationally invariant transformations to the module structure to optimize for various cost metrics (see my previous entry on using an economic model as an optimization strategy). Module flattening takes an entire sub-directory structure and flattens it into a single directory. Rule merging takes two disjoint processes and combines them (increasing speed and resource consumption). Rule sequentialization split rules up to conserve resources. Place and route optimizations should also be done, moving modules around within the FPGA to optimize for speed, power and area.
I will put it all online as soon as I write better documentation and work out some demos. If you're interested in seeing the GCD demo please contact me! The most immediate next step I'd like to take is to compile a streaming language into this world of guarded atomic actions.
Sunday, December 24, 2006
low power filters using polyphase decomposition
Polyphase decomposition is a method of transforming a filter into k filters running at 1/k of the sampling rate. The benefit of polyphase decomposition is that reducing the sampling rate of a filter by a factor of k, reduces the power required to implement the filter by a factor of k^3. Of course if we require k times more filters to implement the system, we may only get a k^2 power benefit. I have to play with some real systems to get data.
Friday, December 01, 2006
Asynchronous, Adiabatic Systems
I've been reading a bunch of papers about Adiabatic, Asynchronous Logic systems and Optical interconnect and switching. These seems like three interesting methods that will alleviate the speed / power tradeoff.
When most people in the computing world hear "SOA" they think service oriented architecture. For the real EE geeks, Semiconductor Optical Amplifier may come to mind. Optical circuits could potentially run 100s of times faster than electronic components and consume very little interconnect power.
Adiabatic systems recover the energy used to perform a function by using clocks as 1 and 0 and maintaining a copy of the function inverse so that there is no entropy change in the system. The result is that very little energy is lost by the system. As the time for the transition approaches infinite, the energy consumed by the function approaches 0. The amount of energy consumed is dependent on the square of the rate of transition. Since more logic is required to compute the inverse there is an area tradeoff. Additionally, energy must be injected into the system to make up for the switching rate which adds complexity to the system design.
Asynchronous systems do not have a clock, and must rely upon asynchronous handshake among communicating components to function correctly. This asynchronous handshake could potentially provide the energy required for an adiabatic circuit to function. I've heard of Achronix making highspeed asynchronous FPGAs. I'm not sure if asynchronous, adiabatic FPGAs exist yet, but I'm willing to bet they will eventually.
I've been concocting an asynchronous FPGA programming method based on rules and guarded atomic actions. Two points in there worth noting: the lumped RAM and router view of an FPGA and the use of an FSM to locally manage the routing table of an FPGA. Locally managed routing presents a miniature microcoded architectures to sequentially implement functions, trading off functional units for RAM and thus enabling "virtualized" structural recursion.
Asynchronous FPGA research at Cornell
Some references on Adiabatic Logic:
Asymptotically Zero Energy Computing Using Split-Level Charge Recovery Logic
Adiabatic CMOS gate and adiabatic circuit design for low-power applications
When most people in the computing world hear "SOA" they think service oriented architecture. For the real EE geeks, Semiconductor Optical Amplifier may come to mind. Optical circuits could potentially run 100s of times faster than electronic components and consume very little interconnect power.
Adiabatic systems recover the energy used to perform a function by using clocks as 1 and 0 and maintaining a copy of the function inverse so that there is no entropy change in the system. The result is that very little energy is lost by the system. As the time for the transition approaches infinite, the energy consumed by the function approaches 0. The amount of energy consumed is dependent on the square of the rate of transition. Since more logic is required to compute the inverse there is an area tradeoff. Additionally, energy must be injected into the system to make up for the switching rate which adds complexity to the system design.
Asynchronous systems do not have a clock, and must rely upon asynchronous handshake among communicating components to function correctly. This asynchronous handshake could potentially provide the energy required for an adiabatic circuit to function. I've heard of Achronix making highspeed asynchronous FPGAs. I'm not sure if asynchronous, adiabatic FPGAs exist yet, but I'm willing to bet they will eventually.
I've been concocting an asynchronous FPGA programming method based on rules and guarded atomic actions. Two points in there worth noting: the lumped RAM and router view of an FPGA and the use of an FSM to locally manage the routing table of an FPGA. Locally managed routing presents a miniature microcoded architectures to sequentially implement functions, trading off functional units for RAM and thus enabling "virtualized" structural recursion.
Asynchronous FPGA research at Cornell
Some references on Adiabatic Logic:
Asymptotically Zero Energy Computing Using Split-Level Charge Recovery Logic
Adiabatic CMOS gate and adiabatic circuit design for low-power applications
Friday, November 24, 2006
Catalyst Accelerated Computing
Catalyst Accelerated Computing has a website. Well sort of. We submitted our executive summary into the MIT $1K competition on Tuesday. We're going to build prototype applications over January. I've been doing my research into the other companies in the "accelerated computing" arena: the best way to stay ahead of the competition is to keep a good scoreboard. That and midterms is why I haven't posted anything in a while.
I've been researching power-optimized partitioning on tiled architectures. Something will come out of that soon.
I've been researching power-optimized partitioning on tiled architectures. Something will come out of that soon.
Friday, November 03, 2006
superscalar OoOE vs multi-core with software scheduling
I have a test in computer archi-torture tomorrow and did a problem that asked us to determine the minimum number of cycles to execute a typical iteration of a particular loop on a superscalar processsor with out of order execution under different assumptions. In the "best case" we were allowed to use as many functional units and memory ports as required and are allowed to fetch and commit as many instructions as we want.
As the number of memory ports, functional units and simultaneous instructions rise, the overhead required to manage the re-order-buffer and register renaming on such a behemoth hardware precludes hardware scheduling as the optimal strategy. Especially since we nearly always run code that has executed before, it seems an awful waste of energy to redo the scheduling in hardware due to the requirement for random instruction issue. Granted, multi-threading on a single core produces the effect of random issue, though especially since we are making the transition towards multi-core, the assumption of random issue should be revisited.
Reduction of scheduling overhead can be accomplished by running the data-flow scheduler as a software process either during compilation or during the phase when an instruction page is loaded into the instruction cache. If we use software compilation for such a VLIW processor then the operating system must manages a file-system of OoOE schedules for every function executed and so that an instruction page fetch automatically fetches system optimized schedules. This is practical because bulk memory for such storage is cheap.
With infinitely many renaming slots, our execution schedule in a superscalar processor resembles a Verilog netlist for the optimal pipeline of our system. To support a large number of virtual registers it would be necessary to "delocalize" register files. Mapping virtual registers to physical registers is now more akin to FPGA place-and-route and may be optimized using similar algorithms.
We must also produce a variety of local caches to support loading and storing of operands and results. We should have the ability to escape to a main memory system on a cache miss (perhaps an on-chip level 2 cache that triggers an interrupt on a second miss).
Once we succumb to software optimized hardware scheduling, it's a small logical step to say that our hardware should allow some amount of reconfigurability to maximize functional unit utilization. The structure of such a hardware device would more closely resemble an FPGA than a single core superscalar processor.
All of this ignores branching of course, which presents an interesting and complicated control problem. More on this another day...
As the number of memory ports, functional units and simultaneous instructions rise, the overhead required to manage the re-order-buffer and register renaming on such a behemoth hardware precludes hardware scheduling as the optimal strategy. Especially since we nearly always run code that has executed before, it seems an awful waste of energy to redo the scheduling in hardware due to the requirement for random instruction issue. Granted, multi-threading on a single core produces the effect of random issue, though especially since we are making the transition towards multi-core, the assumption of random issue should be revisited.
Reduction of scheduling overhead can be accomplished by running the data-flow scheduler as a software process either during compilation or during the phase when an instruction page is loaded into the instruction cache. If we use software compilation for such a VLIW processor then the operating system must manages a file-system of OoOE schedules for every function executed and so that an instruction page fetch automatically fetches system optimized schedules. This is practical because bulk memory for such storage is cheap.
With infinitely many renaming slots, our execution schedule in a superscalar processor resembles a Verilog netlist for the optimal pipeline of our system. To support a large number of virtual registers it would be necessary to "delocalize" register files. Mapping virtual registers to physical registers is now more akin to FPGA place-and-route and may be optimized using similar algorithms.
We must also produce a variety of local caches to support loading and storing of operands and results. We should have the ability to escape to a main memory system on a cache miss (perhaps an on-chip level 2 cache that triggers an interrupt on a second miss).
Once we succumb to software optimized hardware scheduling, it's a small logical step to say that our hardware should allow some amount of reconfigurability to maximize functional unit utilization. The structure of such a hardware device would more closely resemble an FPGA than a single core superscalar processor.
All of this ignores branching of course, which presents an interesting and complicated control problem. More on this another day...
Subscribe to:
Posts (Atom)