Computer Engineering and Systems Group

Interdisciplinary Extensions

 

I conduct several point research efforts in multi-disciplinary areas. Among such areas are decoders for WiMAX, code generators for fix-free codes, and LDPC and MIMO decoders. We have also worked on the routing and wavelength assignment (RWA) problem in optical networks, using Boolean Satisfiability to solve the problem efficiently. Additionally, we have developed efficient realizaitons of the multiple constant multiplication (MCM) problem for FFT. In the space of internet protocol (IP) research, we have developed techniques to compress IP routing tables on-the-fly using distance one merge heuristics, and also developed a very fast and efficient Ternary CAM for IP routing. We have also conducted research in FPGA implementations of radar signal processors, and developed a prototype processor for weather radar.

 

Publications, patents and artefacts:

  • Invited Paper “Highly Parallel Decoding of Space-Time Codes on Graphics Processing Units”, Bollapalli, Wu, Gulati, Khatri, Calderbank. Annual Allerton Conference on Communication, Control and Computing, 2009, Urbana, IL. Sept 30 – Oct 2, 2009. In this paper, we implement the decoding tasks of a WiMAX base station on a GPU. We show that the GPU implementation is about 700X faster than a serial implementation. The results are significant, since they could dramatically reduce the cost of electronics in the base station.
  • “A SAT-based Scheme to Determine Optimal Fix-free Codes”, Abedini, Khatri, Savari. Data Compression Conference (DCC), Snowbird, UT, Mar 24-26, 2010. Best student paper award. In this paper, we develop SAT based techniques to develop optimal fix-free codes. By expressing the code constraints as SAT formulae, and an efficient SAT solver is employed to find the codes.
  • “High-throughput VLSI Implementations of Iterative Decoders and Related Code Construction Problems”. Nagarajan, Laendner, Jayakumar, Milenkovic, Khatri. Springer Journal of VLSI Signal Processing, vol 49, number 1, Oct 2007, pp 185-206. A shorter version of this paper appeared, in GlobeComm 2004, pp. 361-365. This effort reports the results of a custom-IC implementation of an LDPC decoder. The approach reduces routing congestion by careful code construction, and improves over standard cell based implementations in terms of power, delay as well as area.
  • “VLSI Implementation of a Staggered Sphere Decoder Design for MIMO Detection”, Bhagawat, Ekambavanan, Das, Choi, Khatri. 45th Annual Allerton Conference on Communication, Control and Computing, Sept 26-28, 2007, Urbana, IL, pp. 228-235. A custom IC implementation of a sphere decoder is undertaken in this paper. Compared to existing approaches, our approach achieves significantly better throughput per unit power or throughput per unit area.
  • “A Boolean Satisfiability based Solution to the Routing and Wavelength Assignment Problem in Optical Telecommunication Networks”, Valavi, Saluja, Khatri. International Conference on Communications (ICC), May 16 – 20 2005, Seoul, pp. 1802-1806. We cast the RWA problem as a SAT instance, and test it on networks with and without wavelength translation capabilities at the nodes. Results are 3-4 orders of magnitude faster than existing approaches.
  • “Efficient Arithmetic Sum-of-Product (SOP) Based Multiple Constant Multiplication (MCM) for FFT”, Karkala, Wanstrath, Lacour, Khatri. International Conference on Computer-Aided Design (ICCAD) 2010, San Jose, CA. pp.735~738. This paper utilizes a SOP based approach to design a MCM circuit. The partial products are reduced using a partial Max-SAT formulation by exploring MSD based alternatives to realize coefficients. The area and delay results are significantly better than the adder-cascade based existing approaches
  • “Practical & Real Time IP Routing Table Compression – Extending algorithms from digital logic synthesis”. Bollapalli, Khatri. Published by LAP Lambert Academic Publishing, Jan 2012, pp 68. ISBN 978-3847321521. This book reports our work on using efficient logic approaches to perform on-the-fly routing table compression for IP networks.
  • “A Fast Ternary CAM Design for IP Networking Applications”, Gamache, Pfeffer, Khatri. 12th International Conference on Computer Communications and Networks (IC3N-03), Dallas, TX, October 2003, pp. 434-439. Selected among the finalists for the best paper award at the conference. In this paper, we design a ternary CAM IC, based on a very fast, pipelined longest prefix match circuit. The resulting IC operates at twice the line rate as compared to the best TCAM IC available at the time of publication.
  • “A Generic Radar Processor Design Using Software Defined Radio”, Brimeyer, Martin, Loew, Farquharson, Khatri, Paul. 33rd American Meteorology Society (AMS) Conference on Radar Meteorology, Aug 6-10, 2007, Cairns, Australia. In this paper, we present a highly configurable, power-efficient radar signal processor for weather applications.
  • “FPGA Based Signal Processing Platform For Weather Radar”, Paul, Khatri, Martin, Brimeyer, Loew, Vivekanandan. International Geoscience and Remote Sensing Symposium (IGARSS) 2007, July 23-27, Barcelona, Spain. This paper reports the results from an FPGA based implementation of a weather radar processor that we conducted. This processor was driven by a PCI interface, and was verified to operate correctly.