Annual Review 2010 > Division of Computer Engineering

Computer Organization Laboratory

Toshiaki Miyazaki

Professor

Satoshi Nishimura

Associate Professor

Hiroshi Saito

Assistant Professor

The following researches are progressed in Computer Organization Laboratory:

Toshiaki Miyazaki:

has mainly two topics as follows:

Satoshi Nishimura:

Hiroshi Saito:

Our research interests are design of asynchronous circuits and its automation. Asynchronous circuits are circuits where circuit components are controlled by pairs of local handshake signals instead of a global clock signal. Because of the absence of a global clock signal, asynchronous circuits are low power and low electromagnetic interference compared to synchronous counter parts which use global clock signals. Our research topics are as follows.

Refereed Proceedings Papers

[hiroshis-01:2010]

H. Saito, N. Hamada, T. Yoneda, and T. Nanya. A floorplan method for asynchronous circuits with bundled-data implementation on FPGAs. In Proc. International Symposium on Circuits and Systems, pages 925-928, 2010.

This paper proposes a floorplan method for asynchronous circuits with bundleddata implementation on FPGAs (Field Programmable Gate Arrays). The proposed method minimizes the delay of the control circuit while considering timing constraints required for bundled-data implementation. Through the implementation of the proposed method, this paper evaluates the proposed method in terms of performance and area for generated floorplans.

[miyazaki-01:2010]

T. Miyazaki and D. Shitara. Automatic Damaged-Function Alternation among Wireless Sensor Nodes. In Proc. 6th International Conference on Networked Computing and Advanced Information Management (NCM2010), pages 557-562, August 2010.

We propose a distributed algorithm for function alternations, which enables sensor nodes to take over the damaged functions of their neighboring sensor nodes dynamically in a wireless sensor network. In this paper, after introducing the concept of the function alternation, the algorithm is explained in detail with some evaluation results. Comparing the results obtained using the proposed algorithm with those obtained using non-function alternation methods shows that the proposed algorithm makes the initial functionality of each sensor function sustainable even if some sensor nodes are damaged.

[miyazaki-02:2010]

Y. Endo and T. Miyazaki. Sensor Node Localization Using Weighted and Iterative Maximum Likelihood. In Proc. IEEE Sensors 2010 Conference (Sensors 2011), pages 2033-2036, November 2010.

We propose a localization method based on an enhanced maximum likelihood (ML) method, which uses the probability density function of radio signal strength indicators (RSSIs). ML is a method used for estimating node location with high accuracy. However, it often requires a large number of anchor nodes, which results in a high cost. To solve this problem, we introduce two key features into the ordinary ML method: iterative multilateration and certainty weight. The former enables the localization of nodes, which cannot directly obtain sufficient information from anchors to estimate their own location, by using the neighboring nodes with already estimated locations as pseudo-anchors (PAs). The latter provides high accuracy by weighting the location of the PA depending on its certainty. The proposed method performs localization in a distributed manner and has high scalability. The evaluation results show that our method can estimate many node locations with a higher accuracy than the original ML.

[miyazaki-03:2010]

T. Miyazaki, D. Shitara, Y. Endo, Y. Tanno, H. Igari, and R. Kawano. Die-hard Sensor Network: Robust Wireless Sensor Network Dedicated to Disaster Monitoring. In Proc. ACM The 5th International Conference on Ubiquitous Information Management and Communication (ICUIMC2011), page http://doi.acm.org/10.1145/1968613.1968678, February 2011.

In this paper, a new type of wireless sensor network system, called die-hard sensor network, is described. The system can automatically monitor a disaster-hit region by scattering many sensor nodes in the region. To realize the system, three new mechanisms have been developed. If a sensor node is unable to perform certain functions, the first mechanism-function alternation-enables its neighboring sensor nodes to automatically take over these functions. Once our system is deployed, it performs uninterrupted surveillance of the disaster-hit region through this mechanism even if some of the sensor nodes suddenly die. The second mechanism is a multi-sink and multi-hop data transfer protocol that realizes reliable data transfer. The third mechanism is sensor node localization. The locations of almost all scattered sensor nodes can be estimated using only a few anchors, i.e., nodes whose positions are known. In this paper, we explain each novel mechanism, present some evaluation results, and introduce a prototype system that employs the mechanisms.

[miyazaki-04:2010]

J. Terazono, H. Fukuhara, R.Fujita, I. Koseda, T. Miyazaki S. Saito, and T. Hayashi. Service Oriented Architecture realized by a Messaging Network. In Proc. the 12th IEEE/IFIP Network Operations and Management Symposium (NOMS 2010), pages 934-937, April 2010.

This paper introduces an approach to realize service-oriented architecture (SOA) governance using a messaging network. The proposed solution uses a messaging network with a structured overlay. The messaging network is XML-based, and is an actual implementation of a content-based network. The proposed scheme provides a network-centric approach to ensure SOA governance by use of a common proactive scheme on the network infrastructure.

[miyazaki-05:2010]

D. Shitara, T. Miyazaki, and H. Igari. A Function Alternation Algorithm for Wireless Sensor Networks. In Proc. IEEE AINA2010 Workshop, pages 650-655, April 2010.

We propose a distributed algorithm to realize an automatic function alternation among sensor nodes. With this algorithm, the function of a damaged sensor node is dynamically taken over by a neighboring sensor node in order to maintain the initial functionality of a wireless sensor network. Each sensor node calculates an indicator value that represents the node's suitability as a candidate to alternate the function of the damaged node. By exchanging this indicator value with other neighboring nodes, the sensor node with the largest indicator value actually takes over the function of the damaged node. In this paper, after describing the function alternation algorithm, an application for sensing function alternation is introduced along with some evaluation results. Simulation results show that our algorithm can maintain a balanced distribution of sensing functions even when some sensor nodes are damaged.

[miyazaki-06:2010]

S. G. Sedukhin, A. S. Zekri, and T. Miyazaki. Orbital Algorithms and Unified Array Processor for Computing 2D Separable Transforms. In Proc. 39th International Conference on Parallel Processing Workshops (ICPPW, MCNOC2010), pages 127-134, September 2010.

The two-dimensional (2D) forward/inverse discrete Fourier transform (DFT), discrete cosine transform (DCT), discrete sine transform (DST), discrete Hartley transform (DHT), discrete Walsh-Hadamard transform (DWHT), play a fundamental role in many practical applications. Due to the separability property, all these transforms can be uniquely defined as a triple matrix product with one matrix transposition. Based on a systematic approach to represent and schedule different forms of the n n ? n matrix-matrix multiply-add (MMA) operation in 3D index space, we design n matrix-matrix multiply-add (MMA) operation in 3D index space, we design new orbital highly-parallel/scalable algorithms and present an efficient n new orbital highly-parallel/scalable algorithms and present an efficient n ? n unified n unified array processor for computing any narray processor for computing any n?n forward/inverse discrete separable transform n forward/inverse discrete separable transform in the minimal 2n time-steps. Unlike traditional 2D systolic array processing, all n2 register-stored elements of initial/intermediate matrices are processed simultaneously by all n2 processing elements of the unified array processor at each time-step. Hence the proposed array processor is appropriate for applications with naturally arranged multidimensional data such as still images, video frames, 2D data from a matrix sensor, etc. Ultimately, we introduce a novel formulation and a highly-parallel implementation of the frequently required matrix data alignment and manipulation by using MMA operations on the same array processor so that no additional circuitry is needed.

[miyazaki-07:2010]

Y. Tanno and T. Miyazaki. Decentralized Multi-Sink Data Transfer Protocol for Wireless Sensor Networks. In Prof. IEEE AINA2010 Workshop, pages 319-324, March 2011.

In this paper, we propose a multi-sink data transfer protocol for wireless sensor networks, called negotiation-based multi-sink data transfer (NMDT). NMDT is based on the packet flooding method, but the direction of packet flooding in each sensor node is dynamically controlled, taking into consideration the network traffic around the sensor node. Thus, stable sensed data transfer and collection can be performed without packet collisions. After explaining NMDT in detail, we present some evaluation results. According to the evaluation results, NMDT can aggregate sensed data from the sensor nodes by more than 25% as compared to the ordinary flooding method.

Unrefereed Papers

[hiroshis-02:2010]

H. Saito. [Invited paper] Design of Asynchronous Circuits with Bundled-data Implementation on FPGA. In IEICE RECONF Technical Report, pages 157-162, 2011.

[hiroshis-03:2010]

H. Naohiro and H. Saito. Integration of Behavioral Synthesis and Floorplanning for Asynchronous Circuits with Bundled-data Implementation. In Design Gaia, pages 137-142, 2010.

[miyazaki-08:2010]

Y. Tanno and T. Miyazaki. FA multi-sink data transfer protocol for wireless sensor networks. In IEICE Society Conference, volume BS-5-3, September 2009.

[miyazaki-09:2010]

D. Shitara and T. Miyazaki. An Algorithm for Multiple SensingFunction Alternations among Neighboring Sensor Nodes. In IEICE General Conference, volume B-20-2, March 2010.

[miyazaki-10:2010]

Y. Ikegaki, N. Takeishi, T. Miyazaki, and S. Sedukhin. A 3-D Array Processor Tuned to 3-D DCT. In IEICE Technical Report, volume FIIS-09260, June 2009.

[miyazaki-11:2010]

Y. Ikegaki, H. Igarashi, T. Miyazaki, and S. Sedukhin. An effective data I/O mechanism utilizing FIFOs for an array processor. In IEICE Technical Report, volume RECONF2009-61, Jan. 2010.

[miyazaki-12:2010]

D. Shitara and T. Miyazaki. Function Alternation Algorithm in Wireless Sensor Networks. In IEICE Society Conference, volume B-7-31, September 2009.

[miyazaki-13:2010]

H. Igari and T. Miyazaki. An Effective OTAP Method for Multiple Sensor Nodes by Reducing Redundant Packets. In IEICE General Conference, volume B-20-1, March 2010.

[miyazaki-14:2010]

Y. Endo and T. Miyazaki. Iterative Maximum Likelihood Localization for Wireless Sensor Nodes. In IEICE General Conference, volume B-20-45, March 2010.

[miyazaki-15:2010]

Y. Ikegaki, T. Miyazaki, and S. Sedukhin. An FPGA Implementation of a Pipelined Array Processor Dedicated to 3D-DCT. In IEICE General Conference, volume D-6-2, March 2010.

[miyazaki-16:2010]

J. Tazawa, Y. Ikegaki, S. Ishikawa M. Sato, and T. Miyazaki. Highspeed Circuit for Gibbs Sampling. In IEICE General Conference, volume D-6-3, March 2010.

[miyazaki-17:2010]

Y. Tanno and T. Miyazaki. Evaluations of Negotiation-based Multisink Data Transfer Protocol. In IEICE General Conference, volume B-20-20, March 2010.

Grants

[hiroshis-04:2010]

H. Saito. Ministry of Education Scientific Research Fund, 2009-2011.

[hiroshis-05:2010]

T. Yoneda, M. Imai, A. Matsumoto, and H. Saito. Core Research for Evolutional Science and Technology of Japan Science and Technology Corporation, 2008-2013.

[miyazaki-18:2010]

T. Miyazaki. JST A-STEP Feasibility Study, 2010.

[miyazaki-19:2010]

T. Miyazaki. Kayamori Foundation of Informational Science Advancement, 2010-2011.

Academic Activities

[hiroshis-06:2010]

H. Saito, 2010.

Technical Program Committee, 5th International Symposium on Embedded Multicore Systems-on-Chip, IEEE

[hiroshis-07:2010]

H. Saito, 2010.

Associate Editor, IPSJ Transactions on System LSI Design Methodology

[hiroshis-08:2010]

H. Saito, 2010.

Technical Program Committee, Asia South Pacific Design Automation Conference, IEEE/ACM

[miyazaki-20:2010]

T. Miyazaki, 2010.

General Chair, MCSoC-10 (IEEE 4th International Symposium on Embedded Multicore Systems-on-Chip), IEEE

[miyazaki-21:2010]

T. Miyazaki, 1986 present. Member, IPSJ

[miyazaki-22:2010]

T. Miyazaki, 2010.

Steering committee member, Technical Group for Reconfigurable Systems (RECONF), IEICE

[miyazaki-23:2010]

T. Miyazaki, 2010.

Steering Committee Member, CIT2010 (10th International Conference on Computer and Information Technology), IEEE

[miyazaki-24:2010]

T. Miyazaki, 2010.

Steering committee member, Technical Group for Function Integrated Information System (FIIS), IEICE

[miyazaki-25:2010]

T. Miyazaki, 2010.

Technical Program Committee Member, UUWSN2010 (The International Workshop on Ubiquitous UnderWater Sensor Network 2010), IEEE

[miyazaki-26:2010]

T. Miyazaki, 2010.

Reviewer, IEEE Transactions on SMCB

[miyazaki-27:2010]

T. Miyazaki, 1984 present. Member, IEICE

[miyazaki-28:2010]

T. Miyazaki, 1988 present. Member, IEEE (CAS, ComSoc, CS)

[miyazaki-29:2010]

T. Miyazaki, 2010.

Reviewer, IEICE Transactions on Communications

Ph.D., Master and Graduation Theses

[hiroshis-09:2010]

Minoru Iizuka. Graduation thesis: An ASIC Design Support System for Asynchronous Circuits with Bundled-data Implementation, School of Computer Science and Engineering, March 2011.

Thesis Adviser: H. Saito

[hiroshis-10:2010]

Hideki Katabami. Graduation thesis: Designs of OCP Compliant NoC for FPGA, School of Computer Science and Engineering, March 2011.

Thesis Adviser: H. Saito

[miyazaki-30:2010]

Asuka Tanaka. Graduation Thesis: Accelerating Gapped Extension part with Traceback in BLAST using Dedicated Hardware, School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Miyazaki

[miyazaki-31:2010]

Yuki Ikegaki. Master Thesis: 3D-orbital Array Processor Architecture for 3D-DCT and Its System Implementation on an FPGA, Graduate School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Miyazaki

[miyazaki-32:2010]

Yuuki Torii. Master Thesis: Peer-to-Peer Virtual Private Network Establishing Single Virtual Subnet, Graduate School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Miyazaki

[miyazaki-33:2010]

Yuuki Tanno. Master Thesis: Distributed Data Transfer Protocol for Multi-Sink Wireless Sensor Networks, Graduate School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Miyazaki

[miyazaki-34:2010]

Yuki Kasama. Graduation Thesis: Multi-Human Tracking in a Room Using Infrared Sensors, School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Miyazaki

[miyazaki-35:2010]

Shizuka Ishikawa. Graduation Thesis: Hardware-based Acceleration of Word-hit Part in BLAST, School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Miyazaki

[miyazaki-36:2010]

Satoshi Watanabe. Graduation Thesis: Implementation of SoftwareHardware Interaction for a 3D Array Processor Using PCI Interface, School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Miyazaki

[miyazaki-37:2010]

Hidenori Igari. Master Thesis: Remote Configuration of Sensor Nodes Using Wireless Communications, Graduate School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Miyazaki

[miyazaki-38:2010]

Miyuki Sato. Graduation Thesis: An FPGA Implementation of Continuous Dynamic Programming Using Ring Array Architecture, School of Computer Science and Engineering, 2011.

Thesis Adviser: T. Miyazaki

[miyazaki-39:2010]

Liang Zhao. Master Thesis: A Statistical Method Extracting Daily Behavior of a Solitary from Data Continuously Aggregated by Sensors Equipped in Rooms, Graduate School of Computer Science and Engineering, September 2010.

Thesis Adviser: T. Miyazaki

[miyazaki-40:2010]

Hiroshi Igashima. Graduation Thesis: An Effective Implementation of Sensor Node Localization Method Based on Maximum-Likelihood Using Received Signal Strength Indicator, School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Miyazaki

[nisim-01:2010]

Akira Sato. Graduation Thesis: Finger recognition with multi-colored markers, University of Aizu, 2011.

Thesis Adviser: S. Nishimura

[nisim-02:2010]

Yoshiaki Hagane. Master Thesis: A GPU-Based Direct Solver for LargeScale Sparse Linear System, University of Aizu, 2011.

Thesis Adviser: S. Nishimura

[nisim-03:2010]

Masaaki Yoshizawa. Master Thesis: Score Tracking Based on Musical Audio Signals, University of Aizu, 2011.

Thesis Adviser: S. Nishimura

[nisim-04:2010]

Kousuke Sato. Graduation Thesis: A scalable VLSI design for Mersenne Twister on FPGA, University of Aizu, 2011.

Thesis Adviser: S. Nishimura

[nisim-05:2010]

Takanori Sato. Graduation Thesis: An assist tool for fixed-point digital signal processing, University of Aizu, 2011.

Thesis Adviser: S. Nishimura

[nisim-06:2010]

Yuki Yonekawa. Graduation Thesis: Photon-Mapping Rendering Processing on GPU, University of Aizu, 2011.

Thesis Adviser: S. Nishimura

[nisim-07:2010]

Hikaru Sakai. Graduation Thesis: Implementation of a Vector Generator for Real-Time Ray Tracing, University of Aizu, 2011.

Thesis Adviser: S. Nishimura