On 2009-02-09, Timothy Normand Miller wrote: > I was working on something like that a while back. I reasoned that > functional languages without side-effects (like Haskell) make it > straightforward to convert programs into dataflow diagrams. Dataflow > diagrams would be relatively straightforward to convert into Verilog > code that could be converted to logic. A well-designed functional > language could then be made to compile to machine code or to FPGA > hardware as needed for the purposes of optimizing hotspots in > supercomputing applications. (Assuming the communication overhead and > latency are not a problem.) > > Of course, I didn't want my first pass to require some massive AI to > "understand" some Scheme-like code in order to figure out what and how > to convert something, so I wanted language concepts that would make > these things more explicit. There are two major features that I felt > would be necessary to make this work well: > > (1) Distinguish between lists (which are to be pipelined and processed > sequentially) from vector (whose members are intended to be processed > in parallel). (Function input and output arguments would ultimately > be treated as vectors of something.)
That may be reasonably close to how lists and vectors are used in actual code. Furthermore, being aware of the distinction, it should be possible to adapt the programming style. Just as (imperative) programmers are half-aware of the machine code generation, they could be half-aware of the hardware design aspect. So, even though this seems more ambitious than the cited LtU article (in the sense of generality, not design quality), it also embeds the idea of FP as a (fuzzy) hardware design language. > (2) Move from a single anonymous return value to multiple named return > values. This way, arbitrary dataflows could be more easily described > where we don't need compiler smarts to figure out that a list or > vector returned by some function is actually just a container for > multiple return values that may go different places. Talking about Haskell or ML, both records and tuples can be considered fixed size data. The distinction is purely syntactic. It sounds reasonable to not use variable sized types unless needed. I think that is also common practice in statically typed functional languages. > On top of that, I felt the need to give compiler hints (or formal > language constructs) regarding common pipelined processes blocks that > would be implemented in hardware. This led me to a generalization of > the map/reduce paradigm. The map paradigm takes one or more lists > and/or lists of vectors and computes on them in some pipelined way. > The reduce paradigm summarizes some larger collection of numbers into > fewer numbers. So for instance, a dot product function would be given > two lists. The lists would have corresponding members pairwise > multiplied in a map fashion (but also somewhat of a reduction), and > then those results would be passed to a reduce unit that sums them. > These things would easily map to pipeline segments. I can see how this immediately applies to linear algebra, which is already suitable for vector processing. I can see it's also more general, since we're not restricted to numbers. I can't see how far it applies to more general problems. Can tree-like data be flattened? Maybe it must be left up to the programmer to choose the right representation. Two more points, but I'm probably complicating things a bit too much here: (3) Simple list-processing recursive calls can often be rewritten in terms of "fold", which can then be streamed as in (1). Other recursive calls may not be linear, so they'd need a stack, and they'd introduce variable delays. That may or may not be feasible. (4) There could be opportunities of sharing function instances between difference call sites if they are only needed every n cycles or with a low probability. These must be sufficient complex to warrant the routing, multiplexing, and extra busy-logic. _______________________________________________ Open-graphics mailing list [email protected] http://lists.duskglow.com/mailman/listinfo/open-graphics List service provided by Duskglow Consulting, LLC (www.duskglow.com)
