Streaming implementation of a sequential decompression algorithm on an FPGA

ABSTRACT

This paper describes an FPGA based implementation of a real time compression algorithm used in transactions between financial institutions such as exchanges and trading houses. FIX is a protocol that has gained widespread popularity for exchanging financial information such as stock prices and purchases over the Internet. If a financial trader can speed up the processing of these protocols, he can make significant financial profits by buying or selling stocks when there is a lot of variability in the share prices. Our methodology tries to recognize and exploit streaming characteristics of the software design in order to implement a pipelined parallel processing system in reconfigurable hardware. It introduces the concept of caches to keep stream pipelines filled more often. The system implemented on a Xilinx Virtex5 LX110T FPGA shows a 17x speedup in throughput over a software implementation running on a dual core Intel Pentium workstation. These techniques are being developed as part of commercial compiler project to automatically translate software binaries to streaming RTL VHDL systems.

REFERENCES

• 1: FAST Specification 1.x.1, 2006-12-20, FAST ProtocolSM, FIX Protocol Ltd, http://www.fixprotocol.org.
• 2: Field Encoding Specification, 1.0, 2006-1-11, FAST ProtocolSM, FIX Protocol Ltd, http://www.fixprotocol.org.
• 3: FIX 5.0 Specification, FIX Protocol Ltd, http://www.fixprotocol.org.
• 4: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 5: M.A. Franklin, E.J. Tyson, J. Buckley, P. Crowley, J. Maschmeyer, "Auto-pipe and the X language: a pipeline design tool and description language," in Parallel and Distributed Processing Symposium, 2006. IPDPS 2006.
• 6: Maya B. Gokhale , Janice M. Stone , Jeff Arnold , Mirek Kalinowski, Stream-Oriented FPGA Computing in the Streams-C High Level Language, Proceedings of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines, p.49, April 17-19, 2000
• 7: N. Bellas, S.M. Chai, M. Dwyer, D. Linzmeier, "FPGA implementation of a license plate recognition SoC using automatically generated streaming accelerators," in Proc. 20th IEEE International Parallel & Distributed Processing Symposium, 2006.
• 8: R.D. Chamberlain and M.A. Franklin, "Automatic Deployment of Streaming Applications on Hybrid Architectures," in Proc. of 11th High Performance Embedded Computing Workshop, September 2007.
• 9: Roger D. Chamberlain , Joseph M. Lancaster , Ron K. Cytron, Visions for application development on hybrid computing systems, Parallel Computing, v.34 n.4-5, p.201-216, May, 2008 [doi>10.1016/j.parco.2008.03.001]
• 10: Silviu Ciricescu , Ray Essick , Brian Lucas , Phil May , Kent Moat , Jim Norris , Michael Schuette , Ali Saidi, The Reconfigurable Streaming Vector Processor (RSVPTM), Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.141, December 03-05, 2003
• 11: S.M. Chai, N. Bellas, M. Dwyer and D. Linzmeier, "Stream Memory Subsystem in Reconfigurable Platforms," in 2nd Workshop on Architecture Research using FPGA Platforms, 2006.
• 12: The Imagine Stream Processor, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.282, September 16-18, 2002
• 13: William J. Dally , Francois Labonte , Abhishek Das , Patrick Hanrahan , Jung-Ho Ahn , Jayanth Gummaraju , Mattan Erez , Nuwan Jayasena , Ian Buck , Timothy J. Knight , Ujval J. Kapasi, Merrimac: Supercomputing with Streams, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.35, November 15-21, 2003
• 14: W. Thies, M. Karczmarek, and S. Amarasinghe, "StreamIt: A compiler for streaming applications," MIT-LCS Technical Memo LCS-TM-622, Cambridge, MA, 2001.
• 15: Xilinx PCI Express Endpoint Block Plus v1.5 datasheet DS551. Xilinx, Inc. http://www.xilinx.com
• 16: Xilinx Virtex-5 Embedded Tri-Mode Ethernet MAC wrapper v1.3 datasheet DS550, Xilinx, Inc. http://www.xilinx.com

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
binary translation, fix., fpga, hardware-software co-design, streaming architecture, system-on-chip