The 2018 ACM International Symposium on Field-Programmable Gate Arrays was held at the end of February in its usual venue of Monterey, California. In this post I identify a few of my personal highlights from the conference.
Josipovic, Ghosal and Ienne presented “Dynamically-Scheduled High-Level Synthesis,” a very nice piece of work, which reminded me of my old days with Handel-C from Celoxica, which had at its core a similar dynamic scheduling approach described in Page and Luk’s paper “Compiling Occam into FPGAs” from the first ever FPL conference. One of the several ways Lana’s work goes beyond this is the way it deals with memory accesses, which it disambiguates using a Load Store Queue. I found this interesting – it seems to me that there might be much scope to apply techniques I’ve worked on for the static disambiguation, using both polyhedral methods  and separation logic , to the problem of generating enough information to produce specialised Load Store Queues for a particular application.
Dai, Liu and Zhang presented “A Scalable Approach to Exact Resource-Constrained Scheduling Based on a Joint SDC and SAT Formulation.” This paper revisited the popular SDC scheduling heuristic of Cong and Zhang and showed how, by combining it with a SAT solver, one can optimally and efficiently solve resource-constrained scheduling problems arising in High-Level Synthesis. Resource constrained scheduling is hard because of the non-convexity in the problem: one may choose to perform operation A before or after operation B when only wanting to use one instance of a resource. It’s this disjunctive constraint that’s heuristically dealt with in the original SDC paper, for which there exist many ILP formulations, and which the authors address with SAT in this paper. I was intrigued by this paper because the learning of SAT conflict clauses done by the tool appeared to me to be very similar in principle to Gomory cuts made by an ILP solver tackling the same problem, and I wondered whether this observation could be made precise and whether it had value the context of the problem at hand.
Mohajer, Wang and Bazargan presented an intriguing paper “Routing Magic: Performing Computations Using Routing Networks and Voting Logic on Unary Encoded Data.” Instead of using a standard positional radix number system, they proposed using a certain form of unary representation under which all digits with the value 1 occur at the start of a word. This allows certain very efficient computations, notably the computation of arbitrary monotonic functions of a single variable, using no logic – only routing. Multi-input functions and non-monotonic functions do require logic, but they showed for some examples that it’s cheaper to have an exponential number of these tiny logic elements than a polynomial number of the larger logic elements that you would get from positional radix number systems. My suspicion is that the scheme would perform particularly poorly on something like a two-input adder, but the authors presented enough examples to convince the audience that there are cases where it performs well. It was an unusual and thought-provoking presentation.
Zheng, Chen, Zhang and Prasanna presented “A Framework for Generating High-Throughput CNN Implementations on FPGAs.” I enjoyed this paper because it explicitly mixed several important things in any good implementation engineering paper: simple analytical models that provide insight into design, good analysis, and lessons that can be reused beyond the case study under consideration, by other designers for other problems.