Edmund Lab Notebook #158
Replies: 22 comments 21 replies
-
|
Oops, I need to make this a habit to update more. Optional ParametersFirstly, work is mostly done on a new feature for optional parameters, formatted as follows: comp MultComb[#IN_WIDTH, ?#OUT_WIDTH=#IN_WIDTH]<G: L-(G), ?L: 1=G+1>(
@[G, L] left: #IN_WIDTH,
@[G, L] right: #IN_WIDTH,
) -> (
@[G, L] out: #OUT_WIDTH,
) where L > G, #IN_WIDTH <= #OUT_WIDTH, #IN_WIDTH > 0, #OUT_WIDTH > 0;There are still a couple issues though: namely, these have to be made explicit at some point in the evaluation to calyx, possibly in the monomorphize pass. There also may be issues with how they are represented in the IR, but that might need a little discussion. The code currently builds but actually compiling the code leads to Floating Point LibraryBeen working on the floating point library a little bit, and have implemented addition with full parametrization using the following signature: Realised a need for optional parameters mainly while working on the multiplication module, where I wanted to perform a multiply while retaining full precision without sign extending both arguments before hand. Also in general, there are often a lot of not very necessary parameters in a lot of modules providing useful but calculatable information. Ideas, Thoughts, ImpressionsJust a quick list of thoughts I've had about the language that might want discussion:
|
Beta Was this translation helpful? Give feedback.
-
|
Awesome progress on things @UnsignedByte! There are couple of interesting threads here:
|
Beta Was this translation helpful? Give feedback.
-
|
More updates, less work done this week because of a lot of travel related things. I mainly got a lot of bugs fixed and just recently finally managed to have everything compile. Optional ParametersOptional parameters seem to be working well now, there were some issues with elaborating parameters in the monomorphize pass which is where I decided to add things, and until recently externals still did not work very well with elaboration, but now things are mostly passing. FP LibraryOn the side of the library, everything has been done and the tests have also been added to the library; however, they are currently not passing for some unknown reason which I am working on fixing at the moment. FFTWith the FFT module I have been figuring out how most of it will likely work, but I am stuck currently on the twiddle factor generation which I will likely need to research more. The problem is pretty much that it requires you to generate values along a sine wave, which is most easily done using verilog-generating python to generate a properly sized table, in which case the entire FFT would have to be python-generated which I'm not sure is exactly what we are looking for. I am looking into whether macros could be used in some way but I haven't found anything yet. |
Beta Was this translation helpful? Give feedback.
-
|
Great stuff here! Couple of comments:
Yup, I was expecting this sooner or later. This is similar to a problem @gabizon103 has: how do we express ROMs in Filament and provide inputs to them for testing. One possible way forward is using Calyx to write a harness for your code. Calyx does have memories that can be configured with initial values using Calyx's data format. Furthermore, because Filament is compiled to Calyx, it would be easy to integrate them. A different, more generic approach that might work for you but not @gabizon103, is implementing ROMs in Filament directly and changing Filament's test harness to initialize the memories with provided values. We can take a lesson from Calyx here and use the |
Beta Was this translation helpful? Give feedback.
-
|
Would be nice to have some more documentation of the filament library, I just spent over an hour trying to figure out a bug only to realize muxes chose the left argument when the selector was 1, not when it was 0. |
Beta Was this translation helpful? Give feedback.
-
|
Argh, welcome to bleeding edge research! It might be worth reading the implementation in |
Beta Was this translation helpful? Give feedback.
-
|
Possibly allowing negative parameters in some simpler way would be useful in the future? Having to check which of two arguments of a subtraction are greater in order to decide whether to generate a |
Beta Was this translation helpful? Give feedback.
-
|
Possibly! One place this could be challenging is that it would make a future implementation of termination checking (#85) hard to implement. |
Beta Was this translation helpful? Give feedback.
-
|
I guess so but termination checking could already be an issue even with positive-only parameters, for example one where odd numbers are treated differently from even ones. |
Beta Was this translation helpful? Give feedback.
-
Optional ParametersShould be done entirely, no issues as of now. Floating Point LibraryFinished as of now, all tests passing! Both add and mult have been tested with 32 bit floating point only, and exhibit correct behavior. Tests are also added to runt by default. IR - Assume passResearched a bit about how the IR is structured and got the pass started, but working on some egg parsing to possibly expedite the generation of assumptions for custom functions. Currently thinking about localizing everything within |
Beta Was this translation helpful? Give feedback.
-
|
Good stuff! I recommend that we merge your changes first before you start working on something new. On the front of |
Beta Was this translation helpful? Give feedback.
-
|
Would be incredibly nice to have some recursive printing for |
Beta Was this translation helpful? Give feedback.
-
|
There already support for recursively printing |
Beta Was this translation helpful? Give feedback.
-
IR - Assume PassFinished pass and merged! Floating point librarycherrypicked commits and wrote tests, merged! Optional Parameterscherrypicked commits again and merged properly with updated main, also added tests. Compilation passBegan compilation pass, currently working for externals. IR needs work on issues like storing unannotated ports, etc which I plan to work on before continuing work with compilation. I still haven't really looked at the lower pass yet, which means I still have to figure out FSM generation, etc, but progress is coming along slowly. |
Beta Was this translation helpful? Give feedback.
-
|
Excited to see the two features merged! One other thing to keep in mind is #60. This is not currently supported in the existing compilation flow but it would be good to add it sometime soon in the future. I recommend making the basic version work first and then adding the "slow FSM" change as well. |
Beta Was this translation helpful? Give feedback.
-
IR - Compile PassLots of progress so far but I've been having a couple issues that I'm currently working through:
It should be almost done, but I haven't tested anything yet so I hope that isn't a huge issue. All of compliation otherwise is already done (with lower included). |
Beta Was this translation helpful? Give feedback.
-
|
Good progress! See this tracker to get a sense of what’s remaining: #200 Your best friend in understanding how a program needs to be compiled is using the “--log debug” with the normal flow to see how the program is transformed by each pass. Using that, we can answer the questions:
|
Beta Was this translation helpful? Give feedback.
-
|
Regarding testing: you’ll likely find bugs. Test early and often! Similarly, consider committing these changes in multiple PRs so that it’s easier to review! |
Beta Was this translation helpful? Give feedback.
-
Compilation PassMostly finished but having issues with port name generation and connecting events to interface ports properly. Need to work on the info struct in order to save information about port connections, in order to properly connect invoke defined ports and events to their component counterpart in calyx and the IR. Fixed a couple bugs regarding event and port generation for optional events and ports. Just added invoke and instance information to the IR, and will continue adding information for ports and connects. |
Beta Was this translation helpful? Give feedback.
-
Compilation PassCompletely finished and functional at the moment, passing monomorphic tests. Opened some issues about possible new IR features that have yet to be discussed, so currently held back due to that in case the features are removed or changed, which would break the code. Floating pointAdded edge case tests and spent time researching UC berkeley's testfloat. Figured out how to make it work but currently also tabled as it is not super important at the moment. FFTRestarted work on the library, removed old stale pull request. |
Beta Was this translation helpful? Give feedback.
-
|
Would be nice to see some documentation on a couple useful things: How exactly are Similarly, with invoke ports, how are these defined? |
Beta Was this translation helpful? Give feedback.
-
|
Verified these to be true, but maybe we could document these somewhere, possibly in PortOwner? not sure. |
Beta Was this translation helpful? Give feedback.
-
|
Yeah, all the directions are with respect to the signature observed by users of the component. Maybe this is a bit confusing and not useful for the way we use them in the IR? Regardless, we should document this in |
Beta Was this translation helpful? Give feedback.
-
Lower passMerged with all the new features implemented (Foreigns, etc). Bundle Elim PassAlso completed, using the Local Port EliminationCompleted as well, also discovered some issues within the original ast compiler that showed incorrect behavior, but corrected in the IR. Astconv fixBeginning work on compiling the signature first in the double pass. Next stepsHave a couple things I want to work on soon-ish:
|
Beta Was this translation helpful? Give feedback.
-
|
Lots of smaller changes this week! Bundle Elim, Assignment Check, Local Port ElimMerged local port elim into bundle elim, and merged the whole PR into main. Also added a new assignment check pass to assert that every port is written to once and only once.
Info ChangesMerged a change on infos that made them use struct variants and added some casting functions that checked if information was added. Astconv RewriteAstconv was rewritten to compile signatures first before anything else, allowing for recursive and mutually recursive components to compile. Also adds even-odd, a mutually recursive test to make sure things work
Expr and Prop interningAdded simplification rules for prop interning similar to expr interning, and fixed a bug in expr interning that was causing some bugs.
Current WorkI have a couple PRs currently open with a few more IR related features:
|
Beta Was this translation helpful? Give feedback.
-
|
A little late on this weeks updates, but here goes: Visitor updateMerged the pass, which adds a Max States passMoved max states generation function into the utilities file and exposed it as public, also implemented the Let-bound ParametersAdded the ability to define parameters in component using let bindings (
Current Work
|
Beta Was this translation helpful? Give feedback.
-
|
Fantastic stuff! Looking forward to review the changes. |
Beta Was this translation helpful? Give feedback.
-
Frontend Redesign Proposal Noteswant
ideas
File scope
Components
Nodes
Error Handling
Utils
|
Beta Was this translation helpful? Give feedback.
-
FloPoCo Build debuggingSpent a couple hours debugging the flopoco build failures, the eventual issue was that flopoco requires This in turn broke flopoco, and I spent a few hours slogging through logs and debugging installation scripts before I finally realized this. This would have been impossible to find if I had not manually looked through the old logs in
|
Beta Was this translation helpful? Give feedback.
-
HypermapperGot a simple version of hypermapper working for the flopoco FFT this week. Currently, the optimizer varies clock period and flopoco target frequency to minimize the following:
It runs 10 parallel synthesis runs per optimization iteration. If the synthesis doesn't meet timing, I have it set the return values of the function arbitrarily to I'm going to try to get some graphs generated as well (pareto plots, etc) which would be cool to see. |
Beta Was this translation helpful? Give feedback.
-
|
OMG!! This is really freaking exciting @UnsignedByte! Super excited to see what the graphs look like |
Beta Was this translation helpful? Give feedback.
-
Filament Optimization IdeasBasic problem statement: For example, take a fixed point multiply add implemented entirely in filament: comp FixedMultiplyAdd[W, D]<'G: 1>(
X: ['G, 'G+1] W,
Y: ['G, 'G+1] W,
Z: ['G, 'G+1] W,
) -> (
out: ['G+1, 'G+2] W
) {
mult := Mult[W, 2*W](X, Y) // 2*W being the output width here
ext := SignExtend[W, 2*W](Z); // Extend Z before adding
add := Add[2*W, 2*W](mult.out, ext.out);
sliced := Slice[2*W, 2*W-D-1, W-D](add.out); // Slice the necessary bits
R := sliced.out;
}Clearly, we need some delay elements here as Obviously, registering first here would save resources. We would like to have a system (possibly based on SDC modules) to do this sort of optimization automatically. This would mean
This system is different from something in, say, XLS, as these components are still required to satisfy the (possibly complicated) timing constraints of the inputs and outputs, which allow a form of constrained optimization not currently possible in other purely HLS languages. This could allow optimization to integraate with hand-optimized components, even hand laid out or analog parts in the future. |
Beta Was this translation helpful? Give feedback.
-
|
In this example, we would type infer the following: comp FixedMultiplyAdd[W, D]<'G: 1>(
X: ['G, 'G+1] W,
Y: ['G, 'G+1] W,
Z: ['G, 'G+1] W,
) -> (
out: ['G+1, 'G+2] W
) {
// cycle 0
mult := Mult[W, 2*W]<'G, 'G+1>(X, Y) // 2*W being the output width here
multDelay := Delay[2*W]<'G>(mult.out);
zDelay:= Delay[W]<'G>(Z);
// cycle 1
ext := SignExtend[W, 2*W]<'G+1>(zDelay.out); // Extend Z before adding
add := Add[2*W, 2*W]<'G+1>(multDelay.out, ext.out);
sliced := Slice[2*W, 2*W-D-1, W-D]<'G+1>(add.out); // Slice the necessary bits
R := sliced.out;
} |
Beta Was this translation helpful? Give feedback.
-
|
A future possibility would also be to allow the program full control over the output timings using existential parameters. For example, on a system where everything is done combinationally, we could write comp FixedMultiplyAdd[W, D]<'G: 1>(
X: ['G, 'G+1] W,
Y: ['G, 'G+1] W,
Z: ['G, 'G+1] W,
) -> (
out: ['G+L, 'G+L] W
) with {
some L where L >= 0;
} {
mult := Mult[W, 2*W](X, Y) // 2*W being the output width here
ext := SignExtend[W, 2*W](Z); // Extend Z before adding
add := Add[2*W, 2*W](mult.out, ext.out);
sliced := Slice[2*W, 2*W-D-1, W-D](add.out); // Slice the necessary bits
R := sliced.out;
}and expect |
Beta Was this translation helpful? Give feedback.
-
|
Thanks for writing this up!
Wonderful! This is exactly what I was thinking too. I think instead of making this a future goal, we should just make it a part of the default idea. If you provide an existential type with an exact assignment ( |
Beta Was this translation helpful? Give feedback.
-
Notes
|
Beta Was this translation helpful? Give feedback.
-
Physical IRImagine an ASAP scheduling system. In combinational logic, the necessity of pipeline registers arises when the latency of sequential combinational blocks adds up to over a single clock period, Say adders take We can imagine a 2-cycle pipeline of
If we want the compiler to have access to this information there seems to be a fairly nice way to represent this in filament already. Instead of comp Add[W]<'G: 1>(
in0: ['G, 'G+1] W,
in1: ['G, 'G+1] W
) -> (
out: ['G+0.3, 'G+1.3] W
) {...}
comp Mult[W]<'G: 1>(
in0: ['G, 'G+1] W,
in1: ['G, 'G+1] W
) -> (
out: ['G+0.6, 'G+1.6] W
) {...}In this case, a pipeline like this: would become in physical IR, which would then allow the compiler to naturally see that each component occurs as follows:
And thus we can see that the multiplier crosses the cycle boundary, and thus can be retimed using a register (that might look like |
Beta Was this translation helpful? Give feedback.
-
|
I think this is interesting! I like to think about how low-level hardware constraints can be encoded in Filament. This seems to me like it has a flavor of feedback-directed optimization because it wouldn't be possible, even for a specific device, to know the combinational delay of even something simple like an adder of known width. And I think this sort of approach would also fail to account for things like wire or interconnect delays that might be on the critical path in an arbitrary FPGA implementation. Going down this route, it seems like we would want to have some sort of binding from the generated verilog back to source-level Filament constructs, so that when we look at synthesis reports we can tell which Filament modules are on the critical path. This way, the compiler would be able to insert pipeline registers to break up the critical path. I think this approach is necessarily coarser-grain than your example above, since I don't know how we would get the information that an adder takes up x% of a cycle, for example. I know XLS has some FDO features, though I've never used it. Also I think there is some work happening with Calyx profiling (I think the goal is to map Verilog performance information back to ADL code). Maybe either of these works can help inform how something like this would work in Filament. |
Beta Was this translation helpful? Give feedback.
-
|
Yeah, my initial thoughts were obvioiusly just to give a random hand-crafted model for a specific FPGA, but FDO is definitely the long term goal here. I am not sure how much plumbing calyx gives us on this end with flagging different components/etc but I am sure there is a way to do this sort of thing. |
Beta Was this translation helpful? Give feedback.
-
Weekly meeting notes
Filament frontend redesign ideasThis would be the ideal future case, where event bindings can be entirely elided. #[schedule]
comp main<'G: 1>(
in: ['G, 'G+1] 32,
) -> (
out: ['G+4, 'G+5] 32,
) {
double := new Add[32](in, in);
square := new Mult[32](double.out, double.out);
out = square.out;
}But for simplicity of changing the compiler as an initial method, we could instead allow users to define parameters that are set to Note here that existentials are being used in the component at a use location, which would actually fail well-formedness at the moment, maybe instead these should be #[schedule]
comp main2[N]<'G: 1>(
in: ['G, 'G+1] 32,
) -> (
out: ['G+4, 'G+5] 32,
) with {
some A where A > 0;
some B where B > 0;
some C where C > 0;
some D where D > 0;
} {
double := new Add[32]<'G+A, 'G+B>(in, in);
square := new Mult[32]<'G+C, 'G+D>(double.out, double.out);
out = square.out;
A := ??;
B := ??;
C := ??;
D := ??;
}Solving the problemCurrently, this would generate the following conditions (in Physical IR: in: ['G, 'G+1]
add.in0, add.in1: ['G+A, 'G+B]
add.out: ['G+A+AddL, 'G+B+AddL]
square.in0, square.in1: ['G+C, 'G+D]
square.out: ['G+C+MulL, 'G+D+MulL]
out: ['G+4, 'G+5]and thus we would have (in normal typechecking) the following (unsatisfiable) conditions (ignoring component latencies) ['G+A, 'G+B] < ['G, 'G+1]
['G+C, 'G+D] < ['G+A, 'G+B]
['G+4, 'G+5] < ['G+C, 'G+D]Where 0 <= A
// Note that in normal type checking we would have the constraint B >= 1
// The reason we do this is because ['G+A, 'G+B] can occur at any later time due to the possibility of inserting delay components
B >= A + 1 // Delay components have an output availability duration of >= 1. Not sure if the `+1`is necessary.
C >= A+AddL
D >= C + 1
4 >= C+MulLWe can solve this SDC to minimize the number of bits stored in registers. In our case, I think we could do something like |
Beta Was this translation helpful? Give feedback.
-
|
These parameters should only be usable in event bindings. Otherwise, a component may be un-monomorphizable, as we could have circular dependencies. For example, if we have comp Add[P]<'G: 1>(
A: ['G, 'G+1] 32,
B: ['G, 'G+1] 32,
) -> (
C: ['G+L, 'G+L+1] 32
) with {
some L;
}
comp main () -> () {
let P = ?;
add := Add[P](in0, in1);
mul := Mul(in0, in1);
}Then we cannot monomorphize add and mul until we know |
Beta Was this translation helpful? Give feedback.
-
|
Another way to enforce this restriction is only allowing |
Beta Was this translation helpful? Give feedback.
-
Monomorphization Passes...?After a bunch of testing and experiments with the monomorphization pass idea, it seems best to currently push it off to a future total rewrite of the monomorphization stuff. The crux of the issue is the way monomorphization is currently handled. In the current case, we have Alternatively, each pass in monomorphization could generate a new The reason for a multi-pass system is that there are inherently two "languages" inside filament, first being the parameter language, which needs to be monomorphized first (concretizing parameters, unrolling loops, monomorphizing instances) and the second being the actual hardware invokes, existentials, etc which are only users of parameters but never generators. These can be safely monomorphized later, and in the case of SDC, need to be as invoke timings need to be decided after unrolling but can affect existentials like latency. Exisentials create some annoying circular dependencies in the control flow essentially that force us to move things into monomorphization that maybe we otherwise wouldnt. |
Beta Was this translation helpful? Give feedback.
-
Hi, this is a lab notebook for me to just jot down any problems, ideas, etc I have about filament!
Beta Was this translation helpful? Give feedback.
All reactions