Energy-Efficient Pattern Matching Methods on a Fine-Grained Many-Core Platform

Emmanuel O. Adeagbo
Masters Thesis
VLSI Computation Laboratory
Department of Electrical and Computer Engineering
University of California, Davis
Technical Report ECE-VCL-2017-1, VLSI Computation Laboratory, University of California, Davis, 2017.


The matching of one or more occurrences of a keyword within a set of input data is widely used in many datacenter applications such as large string databases, network intrusion detection systems, and search engines. As demand for datacenter performance continues to increase, energy consumption has gone up by nearly 4x within the last decade. It is therefore desirable to have very low energy dissipation per workload with low area overhead and high throughput.

This thesis first presents three energy-efficient methods for searching and filtering streamed data on a fine-grained many-core processor array: parallel, serial, and all–in–one. All three architectures provide programmable flexibility with low energy consumption. Experimental results show that for one keyword search, the parallel and serial architectures consume 2x less energy per workload than the all–in–one architecture. For two or more keyword searches, the all–in–one architecture achieves up to 2.6x higher throughput per area over the parallel architecture, and 25.6x over the serial architecture. Scaled results show that the serial and parallel designs provide 211x increased throughput per area, and yield 155x energy reduction when compared to a traditional processor (Intel Core i7 3667U). The proposed architectures are modular and easily scalable. In addition to the proposed three energy–efficient methods for searching and filtering strings, this thesis also presents two self–adaptive string search filters for further reducing energy consumption and improving throughput of string search via self–reprogramming. Results show that the self–adaptive implementation with separated statistics block achieves about 2.8x to 4x higher throughput and throughput per area on average than the implementation with combined statistics block in statistics mode. Other performance parameters such as energy per workload, throughput and throughput per area of the main filters are approximately equal. Next, this thesis investigates regular expression processing and its applications on the AsAP2 fine-grained many-core processor. Results show that ~99% of activity occurs within the first core of the regular expression filter and less than 27% activity in subsequent cores. The regular expression filters achieve a throughput of 309 MB/s on average when running at the maximum voltage of 1.3 V and 17 MB/s when running at the minimum voltage of 0.675 V. Finally, this thesis provides brief descriptions of completed projects, and future work. The future work focuses on expanding the capabilities of the regular expression work into a key application such as developing a more sophisticated web search engine.



Emmanuel O. Adeagbo, "Energy-Efficient Pattern Matching Methods on a Fine-Grained Many-Core Platform," Masters Thesis, Technical Report ECE-VCL-2017-1, VLSI Computation Laboratory, ECE Department, University of California, Davis, 2017.

BibTeX entry

   author      = {Emmanuel O Adeagbo},
   title       = {Energy-Efficient Pattern Matching Methods on a Fine-Grained Many-Core Platform},
   school      = {University of California, Davis},
   year        = 2017,
   address     = {Davis, CA, USA},
   month       = dec,
   note        = {\url{}}

Support Acknowledgment

This work is supported by UC Davis ECE Department, ST Microelectronics, NSF Grants, SRC GRC Grant 2321.001, NSF CCF Grant No. 1321163, 1018972, 0903549, 0430090, C2S2 Grant 2047.002.014, CAREER Award 0546907, DoD and ARL/ARO grant W911NF-13-1-0090

VCL Lab | ECE Dept. | UC Davis