The gap between the speed of processors and that of memory has been widening for decades and will continue to widen with current technology forecasts. This major obstacle to high-performance computing is traditional overcome using techniques that exploit data locality in memory, such as cache memories. However, a very important class of applications commonly referred to as irregular applications, do not exhibit any locality. Examples of such applications include: (1) sparse linear algebra, widely used in science, engineering, medicine, finances, economic modeling etc; and (2) graph algorithms, used in the modeling and analysis of large data such as social networks and the ab-initio construction of genomes from sequenced material etc. Hardware supported multithreaded execution has been shown to mask the latency to memory, and hence can boost the effective parallelism, by suspending a thread waiting for the result of a memory operation and resuming it when the results are available. By doing so the utilization of the computational units is raised to near 100% resulting in a tremendous speedup of the computation.
This research aims at generating customized hardware for multithreaded execution on configurable devices such as FPGAs. FPGAs (Field Programmable Gate Arrays) are integrated circuits on which arbitrary digital hardware circuits can be configured and reconfigured under software control. Toward this goal, CHAT (Customized Hardware Accelerated Threads) is being developed as a tool that generates a custom multithreaded FPGA processor design tailored for a particular application, based on the C programming language specification of the application. Preliminary results show a potential speedup greater than 10x over traditional memory hierarchy approaches for some irregular applications. The technical deliverables of this project will be: (1) an open-source distributed version of CHAT implemented on high-performance machines with FPGA accelerators; and (2) a detailed analysis of the performance benefits of various compile-time optimizations on various applications.
