Acceleration of the discrete element method on a reconfigurable co-processor

Abstract

Granular materials are important for many different disciplines, e.g. geomechanics, civil engineering and chemical engineering. Many approaches have been used to model their behaviour, but one of the best and most important is the Discrete Element Method (DEM). The DEM was first developed during the 70’s, but its widespread use has been hampered by its extremely computationally demanding nature. The DEM can be run on a parallel computer by farming out different sub-domains onto different processors. However, particles transiting from one sub-domain to another create communication and synchronisation overheads which limit the speed-up achieved by parallel processing. Also, if some cells become much more heavily populated than others, then there will be inefficiencies due to load imbalance between the processors. As a result of these effects, the speed-up achieved by running the DEM on parallel processor computers is far less than linear. This thesis describes work on the acceleration of the DEM using reconfigurable computing. A custom hardware architecture for the DEM has been designed and implemented on a Field Programmable Gate Array (FPGA) mounted on a reconfigurable computing card. The design exploits the low level parallelism of the DEM by using long, wide computational pipelines that compute many arithmetic operations concurrently. It also exploits the high level parallelism by overlapping the main computational tasks using domain decomposition techniques. Speed-ups of a factor of at least 30 per FPGA have been achieved for simulations involving 25,000 to 200,000 particles. A multi-FPGA system has been implemented that allows the full overlap of computation with communication, so that an almost linear speed-up can be achieved as the number of FPGAs is increased. The effect of the short wordlength arithmetic used in the FPGA has been investigated, and the accuracy of the simulations has been found to be acceptable.