Yosi Ben Asher

I am a researcher in: compilers, highlevel synthesis (HLS), parallel programming. I am motivated by two observations: I believe compilers are basically tools to express tradeoffs between scheduling and resources (similar to the time-space pebble-games studied in theoretical computer science). Thus the target architecture is of secondary importance, the compilation of a given program should be done by obtaining an optimized point of the (schedulin_time X hardware_configuration) space. I believe compilers should be implemented in two phases: 1) a source level tradeoff-explorer targeting a virtual tunable hardware architecture (HA); 2) followed by a separate "normal" compiler that schedules and optimizes the code generated by the tradeoff-explorer targeting some real CPU or a circuit. I am still far from reaching this goal, though I have developed few systems to explore such tradeoffs in HLS and few systems that handle source level compilation (e.g., a system that merges independent programs in source level). In particular I need to develop a retargeble compiler whose code generation stage generates assembly instructions on-the-fly thus determining the best HA suitable for the source code it is compiling. Note that this direction differs than Application Specific Instruction Set Processors that have a configurable instruction set since we actually intend to scan all possible HAs. Though retargeble compilers exists, the propose compiler will really explore all possible hardware configurations which is differ than allowing the user to modify the HA changing few parameters. Another attempt I have made in this direction is to show that many of the optimization paths of a compiler can be expressed as pebble-games, hoping to find a unified algorithmic specification for compilers. The ability to compute via re-configurations (directing signals through different edges in a graph) has always fascinated me. A reconfigurable unit basically computes a boolean function in one parallel step: set the re-direction of incoming signals at each node and then propagate a signal through the graph. It took sometime for me to understand that unlike boolean circuits reconfigurable units are not compositional, i.e., the outputs of a reconfigurable unit can not be connected to the input of another unit without violating the one-parallel-step assumption. I believe that a compiler targeting reconfigurable units can overcome this problem. I would like to study HLS systems that target branching programs instead of boolean circuits. I believe that (using novel switching technologies) by doing so we can overcome the ever-growing delays involved with the wires and MUXes that connect the boolean gates in regular circuits. The trick is that via a HLS compiler it will be possible to synthesize such large size branching programs bypassing the need to explicitly design their structure. This goal is closer to be realized I have some breakthroughs in developing necessary compilation techniques.

Email: yosi@cs.haifa.ac.il Phone: 972-4-8240338

I am giving consulting services to industrial companies in the area of compiler optimizations and highlevel synthesis.

These are my current research efforts that are in an advanced stage and will be added to SystemRacer. These are interesting technologies that are part of the quest to make SystemRacer very powerfull HLS system actually targeting complete unrestricted C programs.

My current research projects include:

Compilation techniques from C to Verilog targeting FPGAs:

• Use of modulo-scheduling techniques for generating efficient circuits. I am studying a promising technique that is called Source Level Modulo Scheduling (SLMS).
• Scheduling tradeoffs, namely, for a given set of loops whose expected number of iterations is known, find an optimized hardware configuration (OHC) that does not reduce optimal execution times (clock-frequency*#clock_cycles) significantly.

Compilation techniques from C to branching programs

as opposed to generating circuits that are based on boolean gates

• Algorithmic techniques to efficiently convert boolean circuits to branching programs without increasing the size.
• Porting algorithms for efficient arithmetic operations that were developed for the reconfigurable mesh to branching programs (BP). This effort of synthesizing arithmetic operations to BPs include some novel hight-reduction techniques we are currently being implementing in the LLVM compiler.
• Study the use of Nano-Carbon-Tubes switching devices (CNT-FETs) and Optical couplers switches (OCS) as a way to implement large BPs. The goal is to synthesize large BPs without paying the quadratic RC-delays that would have been obtained had we used boolean-gates and CMOS-FETS to implement the BP (Elmore's delay model).

HLS of multi-threaded code

is an attempt to minimize the use of shared memories in the circuits resulting from HLS of multi-threaded code. In here the focus is on the tradeoff between optimized scheduling and minimal use of shared memory modules.

• Lazy thread generation, a compilation techniques to minimize the number of ParC threads that are implemented by ``real'' threads.
• Generating code that will minimize the BusRd transactions caused by the MESI/MOESI algorithms used in multicore machines to simulate shared memory.

Current Compiler Systems
The HTINY system for source level optimizations and source level HLS
SystemRacer an LLVM based HLS compiler targeting variable pipeline operations and multithreaded code
ParC compiler+simulator for parallel programming of multicore machines

Papers, Courses and Past Projects

• My Journal papers
• My Conference papers
• Students I have/am guiding
• Project in AD HOC routing
• Source level merging Project
• Internet File System Project
• Basic course in compilers
• Course in FPGA designs
• Course in Advanced Compiler Optimizations
• External links

The Htiny System

The HTINY system (Haifa's Tiny) is an extension of Wolfe's Auto parallelizing system. The main goal is to transform it to a full source-level compiler that targets both regular CPUs and synthesized circuits. By a source-level compiler we mean a compiler that does not starts by applying code-generation and whose intermediate representation is the abstract-syntax-tree (AST) rather than RTL instructions. We belive that source-level compilation is the key technology to obtain better compilers that can be used to explore different tradeoffs involved with code/circuit generation. The current system contains the following parts added to the original Tiny:

• A set of loop transformations that can be interactively applied to optimize nested loops. These transformations include: uni-modular transformation, loop interchange, loop tiling, loop skewing, loop fusion, loop peeling, loop distribution, and loop flattening. Several other transformations are available to handle conditional statements including: if-conversion (predication), tail-duplication, lifting if-statements by loop splitting, special unroll and jam of if-statements and some form of speculative simplification of if-then-else statements. There are also few transformations that are related to induction variables (IVR), including: IVR substitution and accumulator expansion. This part is not automated and the user must learn by experience which combinations of loop transformations are useful for a given nested loop. An advanced version of loop-unrolling can be used as well. This version expands array expressions in the unrolled iterations.

• As a separate part the Htiny system has a special synthesis module that synthesize compound loops. In this, we consider a special optimization problem involved with compiling compound loops (combining nested and consecutive sub-loops) with array references to Verilog. Each sub-loop of the compound loop may require a different optimized hardware configuration (OHC) for optimized execution times. For example, one loop requires at least two memory ports and one multiplier for an optimized execution time while another loop may require only one memory port but two multipliers, yet one OHC should be selected for both loops. The goal is to compute a minimal OHC which, based on the different execution frequencies of the sub-loops, is a good compromise between all the conflicting requirements of each sub-loop. Though synthesis of nested loops has been implemented in quite a few systems this aspect has not been considered so far. We avoid the use of Integer Linear Programming (ILP) techniques and instead use a fast space exploration technique that is combined with an efficient variant of list scheduling.

  Another novel aspect of the proposed system is the observation that the real latencies of the hardware units should be considered as variables of the OHC rather than fixed real values as is usually done in high-level synthesis systems. Experimental results show a significant improvement in the OHC without a significant increase in the execution time due to the use of this search procedure. configuration

Modulo scheduling (MS) is a technique in which a loop is parallelized by overlapping different parts of successive iterations. This ability to extract parallelism makes MS an attractive synthesis technique for loop acceleration and is applied as a separate module of HTINY. Current MS scheduling techniques sacrifice execution times in order to meet resource and delay constraints. Let ``ideal'' execution times be the ones that could have been obtained by MS had we ignored resource and delay constraints. Here we pose the opposite problem, which is more suitable for HLS, namely, how to reduce resource constraints without sacrificing the ideal execution time. We focus on reducing the number of memory ports used by the MS synthesis, which we believe is a crucial resource for HLS. In addition to reducing the number of memory ports we consider the need to develop MS techniques that are fast enough to allow interactive synthesis times and repeated applications of the MS to explore different possibilities of synthesizing the circuits. We have formalized the problem of reducing the number of parallel memory references in every row of the kernel by a novel combinatorial setting. The proposed technique is based on inserting dummy operations in the kernel and by doing so, it performs modulo-shift operations such that the maximal number of parallel memory references in a row is reduced. Experimental results suggest improved execution times for the synthesized circuit even compare to commercial tools. The synthesis takes only a few seconds even for large size loops.

HTINY accepts inputs in a Fortran style but can be applied to C-code using a conversion tool. Pointers are not supported and function calls are supported by the loop transformations part but not by the two synthesis parts.. Htiny contains a back-end to x86 machine code.

Some screen-shots of the current system with Xilinx's ISE synthesis tool:

• stage 1:Htiny stage 2:resulting Verilog stage 3:timing report stage 4:schematics

Publications:

• Source Level Modulo Scheduling

SystemRacer

Traditionally, scheduling algorithms for software instructions concentrated on problems such as optimal register usage, branch elimination and instruction level parallelism. However, in the context of hardware synthesis, scheduling algorithms optimize entirely different set of constraints. In hardware synthesis, design frequency, size and power consumption are affected by parameters such as reuse of modules, wire length, longest gate chain, etc. Usually, in high level hardware synthesis, all functional units of the same type have a fixed known ``length'' (number of stages) and the scheduler mainly determines when each unit is activated. We focus on scheduling techniques for the high-level synthesis of pipelined functional units where the number of stages of these operations is a free parameter of the synthesis. This problem is motivated by the ability to create pipelined functional units, such as multipliers, with different pipe lengths. These units have different characteristics in terms of parallelism level, frequency, latency, etc. This work presents the variable pipeline scheduler (VPS). The ability to synthesize variable pipelined units expands the known scheduling problem of high-level synthesis to include a 2D search for a minimal number of hardware units (operations) and their desired number of stages. The proposed search procedure is based on algorithms that find a local minima in a $d$-dimensional grid, thus avoiding the need to evaluate all possible points in the space. We have implemented a C language compiler for VPS. Our results demonstrate that using variable pipeline units can reduce the overall resource usage and improve the execution time.

The system we implemented is based on the LLVM compiler toolkit and is called SystemRacer. The system is comprised of two parts. First, a compiler front-end parses $C$ into the internal compiler representation. Secondly, a synthesis backend creates the hardware description language. In our case, Verilog. The synthesis unit contains the search algorithm which finds the best resources for the given high-level code using the above LS algorithm. We have extended the LLVM optimizations passes in order to expose parallelism. For example, loop-code which is executed on a CPU, may calculate the address of an array before reading from it. In hardware, we are able to calculate this address for the next iteration, in parallel to the current read operation, since they are not dependent. Another example is a pass which takes an arithmetic expression and balances commutative expressions so that more operations can be executed in parallel.

Each type of the LLVM bytecode has a resource reservation table allowing the scheduler to place a given instruction in the 2D table. The reservation tables are generated dynamically based on the current hardware configuration (HC) point that is evaluated. For example, if the current HC contains $pm=4$ (pipeline length of multiplication), then the reservation table of $multiplier_i$ will be $RT_i[mull\_in,0]='X'$ and $RT[mull\_out,4]='X'$ and all other entries in $RT_i[,]$ are empty. The search starts by determining the range of the eight dimensional optimized hardware configuration (OHC) space including the number of arithmetic operations ($m$), memory ports ($r$), and delay factors ($mdf$). For example some point < m=5,pm=1,s=5,ps=1,d=5,pd=1,r=6,mdf=1 > may form the ``lower'' point in the range as it represents maximal resources and minimal delay factors imposing no restrictions on the list scheduler used by the system. The opposit ``upper'' point in the range is < m=1,pm=16,s=1,ps=10,d=1,pd=16,r=1,mdf=5 > is the most desired point as it minimizes the resources and maximizes the delay factors. The LS is initially applied to determine an actual upper bound to the maximal number of resources that can be used for each basic block. This is done by running the list scheduler with infinite resources and recording how many resources were actually used. This helps in reducing the search space for some of the parameters. A random search procedure is activated to find a local minima testing up to $10^4$ OHC points.

A web-site of the current version of SystemRacer (Towards a commercialize version):

• SystemRacer web-site

Current state:

• We are now adding loop-unrolling of while-loops that are advancing pointers. When this is done, while-loops of the form $while(p != NULL){...p=p->next; ... } can be unrolled and synthesized. The main mechanism for applying unrolling of pointered loops has been implemented in the LLVM and was tested (with about 5% improvement over GCC and ICC for regular CPUs), however it still remain to combine it with the synthesis unit.
• We are currently adding threads and synthesis capabilities to generate multiport shared memories. We are mainly focusing in the synthesis of the shared memory needed to execute multi-threaded code.
• System racer also has the ability to synthesize directly from executables, by applying a disassembler to LLVM bytecode and then a pass that extracts array references. Though this is working it is not completed yet.

In conclusion currently SystemRacer supports:

ParC

ParC is a parallel dialect of C similar to OpenMP. Following the emergence of multicore machines I have started to work on developing efficient compiler for ParC programs targeting multicore machines. The main focus of this project is to develop efficient compilation techniques to overcome the large overhead caused by the busRD transactions on the bus of the multicore machine every-time a cache miss occurs. Simple experiments shows that the overhead of using the MESI/MOESI protocols to simulate shared memory can be really high. A simple experiment with two threads updating a common shared array showed that the parallel version is slower by 40% than the sequential execution (see results ). Though ParC is similar to OpenMP it has some unique features that makes it attractive for multicore machines:

• ParC has nested scoping rules that makes the use of shared/private variables implicit using the nested structure of the program. In addition the scoping rules of ParC implies that any access to a local variable of a thread must be implemented as a local memory reference, namely a local cache-hit in a multicore machine. It is thus a challenging task to impose this rule via a compilation scheme, where certain variables are guaranteed to be in the cache of some core.
• ParC has its own threading system that is part of the language, designed to reduce the overhead of managing the threads and the cactus stack to a minimum.
Context-switches are inserted by the compiler in every while-loop that accesses shared variables. This reduces the overhead for managing ParC's threads to a minimum.
• ParC has several constructs that can be used to implement partition arrays, this requires efficient handling of a distributed heap.

Current status of the system is as follows:

• A book describing parallel programming via ParC is close to completion.
• A simulator for ParC programs including a simulation of the MESI/MOESI protocols has been implemented.
• A technique for lazy thread generation has been developed for ParC. I believe that lazy-threads is an essential technique in overcoming the large overhead of MESI/MOESI in multicore machines.