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:

def SheetNonBlockingAssignments(Sh):
    valdic = {}
    for key,value in Sh.Cells.iteritems():
        valdic[key]=value.Value

    for cell in Sh.Cells.values():
        try:
            if (cell.Formula == ''):
                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)

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:

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 :)

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.