Efficient Multiplexer Networks for Field-Data Extractors and Their Evaluations

• ITO Koki

  Dept. of Computer Science and Communications Engineering, Waseda University

• KAWAMURA Kazushi

  Dept. of Computer Science and Communications Engineering, Waseda University

• TAMIYA Yutaka

  Fujitsu Laboratories Ltd.

• YANAGISAWA Masao

  Dept. of Computer Science and Communications Engineering, Waseda University

• TOGAWA Nozomu

  Dept. of Computer Science and Communications Engineering, Waseda University

Abstract

As seen in stream data processing, it is necessary to extract a particular data field from bulk data, where we can use a field-data extractor. Particularly, an (M,N)-field-data extractor reads out any consecutive N bytes from an M-byte register by connecting its input/output using multiplexers (MUXs). However, the number of required MUXs increases too much as the input/output byte widths increase. It is known that partitioning a MUX network leads to reducing the number of MUXs. In this paper, we firstly pick up a multi-layered MUX network, which is generated by repeatedly partitioning a MUX network into a collection of single-layered MUX networks. We show that the multi-layered MUX network is equivalent to the barrel shifter from which redundant MUXs and wires are removed, and we prove that the number of required MUXs becomes the smallest among MUX-network-partitioning based field-data extractors. Next, we propose a rotator-based MUX network for a field-data extractor, which is based on reading out a particular data in an input register to a rotator. The byte width of the rotator is the same as its output register and hence we no longer require any extra wires nor MUXs. By rotating the input data appropriately, we can finally have a right-ordered data into an output register. Experimental results show that a multi-layered MUX network reduces the number of required gates to construct a field-data extractor by up to 97.0% compared with the one using a naive approach and its delay becomes 1.8ns-2.3ns. A rotator-based MUX network with a control circuit also reduces the number of required gates to construct a field-data extractor by up to 97.3% compared with the one using a naive approach and its delay becomes 2.1ns-2.9ns.

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E100.A (4), 1015-1028, 2017

  The Institute of Electronics, Information and Communication Engineers

Keywords

• field-data extractor
• multiplexer network
• partitioning
• rotator

Details

• CRID: 1390282681288108544
• NII Article ID: 130005529555
• DOI: 10.1587/transfun.e100.a.1015
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E100.A/4/E100.A_1015/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed