Professor
Department of Computer Science
Meiji University, Kawasaki, Japan

 

 

Webpage

Index Generation Functions : Logic Synthesis for Pattern Matching

Thursday, 10 December 2015 at 9:00 in room BC 420

 

Abstract:

High-speed pattern matching is implemented with conventional memories. Using the concept of index generation function, the total amount of memory is reduced. Applications to network router, terminal access controller, and computer virus scanner are shown.

The outline of the talk is as follows: 1) definition of index generation functions; 2) reduction of the number of variables for incompletely specified index generation functions; 3) statistical property of index generation functions; 4) linear decomposition of index generation functions; 5) index generation unit (IGU); 6) applications; and 7) current projects.

Part of this talk appeared in T. Sasao, "Memory-Based Logic Synthesis," (Springer 2011), ICCAD-2008, ISMVL-2011, ASPDAC-2012, DATE-2012, ARC-2012, ISMVL-2012, ARC-2013, ISMVL-2015, and IWLS-2015.

About the speaker:

Tsutomu Sasao received the B.E., M.E., and Ph.D. degrees in Electronics Engineering from Osaka University, Osaka Japan, in 1972, 1974, and 1977, respectively. He has held faculty/research positions at Osaka University, Japan; IBM T. J. Watson Research Center, Yorktown Heights, NY; the Naval Postgraduate School, Monterey, CA; and Kyushu Institute of Technology, Iizuka, Japan. Now, he is a Professor at the Department of Computer Science, Meiji University, Kawasaki, Japan.

His research areas include logic design and switching theory, representations of logic functions, and multiple-valued logic.

He has published more than 10 books on logic design including, Logic Synthesis and Optimization, Representation of Discrete Functions, Switching Theory for Logic Synthesis, Logic Synthesis and Verification, and Memory-Based Logic Synthesis, in 1993, 1996, 1999, 2001, and 2011, respectively.

He has served as Program Chairman for the IEEE International Symposium on Multiple-Valued Logic (ISMVL) many times. Also, he was the Symposium Chairman of the 28th ISMVL held in Fukuoka,Japan, in 1998.

He received the NIWA Memorial Award in 1979, Takeda Techno-Entrepreneurship Award in 2001, and Distinctive Contribution Awards from IEEE Computer Society MVL-TC for papers presented at ISMVLs in 1986, 1996, 2003, 2004, and 2013. He has served as an associate editor of the IEEE Transactions on Computers. He is a Fellow of the IEEE.