The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Applications of Reprogrammability in Algorithm Acceleration

Matti Tommiska

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Department of Electrical and Communications Engineering for public examination and debate in Auditorium S3 at Helsinki University of Technology (Espoo, Finland) on the 18th of March, 2005, at 12 o'clock noon.

Overview in PDF format (ISBN 951-22-7527-9)   [934 KB]
Dissertation is also available in print (ISBN 951-22-7526-0)

Abstract

This doctoral thesis consists of an introductory part and eight appended publications, which deal with hardware-based reprogrammability in algorithm acceleration with a specific emphasis on the possibilities offered by modern large-scale Field Programmable Gate Arrays (FPGAs) in computationally demanding applications.

The historical evolution of both the theoretical and technological paths culminating in the introduction of reprogrammable logic devices is first outlined. This is followed by defining the commonly used terms in the thesis. The reprogrammable logic market is surveyed, and the architectural structures and the technological reasonings behind them are described in detail. As reprogrammable logic lies between Application Specific Integrated Circuits (ASICs) and general-purpose microprocessors in the implementation spectrum of electronics systems, special attention has been paid to differentiate these three implementation approaches. This has been done to emphasize, that reprogrammable logic offers much more than just a low-volume replacement for ASICs.

Design systems for reprogrammable logic are investigated, as the learning curve associated with them is the main hurdle for software-oriented designers for using reprogrammable logic devices. The theoretically important topic of partial reprogrammability is described in detail, but it is concluded, that the practical problems in designing viable development platforms for partially reprogrammable systems will hinder its wide-spread adoption.

The main technical, design-oriented, and economic applicability factors of reprogrammable logic are laid out. The main advantages of reprogrammable logic are their suitability for fine-grained bit-level parallelizable computing with a short time-to-market and low upfront costs. It is also concluded, that the main opportunities for reprogrammable logic lie in the potential of high-level design systems, and the ever-growing ASIC design gap. On the other hand, most power-conscious mass-market portable products do not seem to offer major new market potential for reprogrammable logic.

The appended publications are examined and compared to contemporaneous research at other research institutions. The conclusion is that for relatively wide classes of well-defined computation problems, reprogrammable logic offers a more efficient solution than a software-centered approach, with a much shorter production cycle than is the case with ASICs.

This thesis consists of an overview and of the following 8 publications:

  1. M. Tommiska and J. Vuori. 1996. Hardware implementation of GA. In: Proceedings of the 2nd Nordic Workshop on Genetic Algorithms. Vaasa, Finland, 19-23 August 1996, pages 71-78. © 1996 by authors.
  2. M. Tommiska, M. Loukola, and T. Koskivirta. 1999. An FPGA-based implementation and simulation of the AAL type 2 receiver. Journal of Communications and Networks 1, number 1, pages 63-67. © 1999 Korean Institute of Communication Sciences (KICS). By permission.
  3. M. Tommiska. 2000. Area-efficient implementation of a fast square root algorithm. In: Proceedings of the Third IEEE International Caracas Conference on Devices, Circuits and Systems. Cancun, Mexico, 15-17 March 2000, pages S18-1 - S18-4. © 2000 IEEE. By permission.
  4. M. Tommiska and J. Skyttä. 2001. Dijkstra's shortest path routing algorithm in reconfigurable hardware. In: G. Brebner and R. Woods (editors), Proceedings of the 11th Conference on Field-Programmable Logic and Applications (FPL 2001). Belfast, Northern Ireland, UK, 27-29 August 2001, pages 653-657. © 2001 Springer-Verlag. By permission.
  5. M. Tommiska, J. Tanskanen, and J. Skyttä. 2001. Hardware-based adaptive general parameter extension in WCDMA power control. In: Proceedings of the 54th IEEE Vehicular Technology Conference (VTC 2001 Fall). Atlantic City, NJ, United States, 7-11 October 2001, volume 4, pages 2023-2027. © 2001 IEEE. By permission.
  6. A. Hämäläinen, M. Tommiska, and J. Skyttä. 2002. 6.78 gigabits per second implementation of the IDEA cryptographic algorithm. In: M. Glesner, P. Zipf, and M. Renovell (editors), Proceedings of the 12th Conference on Field-Programmable Logic and Applications (FPL 2002). Montpellier, France, 2-4 September 2002, pages 760-769. © 2002 Springer-Verlag. By permission.
  7. K. Järvinen, M. Tommiska, and J. Skyttä. 2003. A fully pipelined memoryless 17.8 Gbps AES-128 encryptor. In: Proceedings of the 11th International Symposium on Field-Programmable Gate Arrays (FPGA 2003). Monterey, CA, United States, 24-26 February 2003, pages 207-215.
  8. M. Tommiska. 2003. Efficient digital implementation of the sigmoid function for reprogrammable logic. IEE Proceedings – Computers and Digital Techniques 150, number 6, pages 403-411. © 2003 IEE. By permission.

Keywords: reprogrammable logic, field programmable gate arrays, digital design, genetic algorithms, communications protocols, digital signal processing, hardware arithmetic, cryptographic implementations

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2005 Helsinki University of Technology

Last update 2011-05-26