Computer Organization Laboratory

Tosiaki 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: Die-hard sensor network is a wireless sensor network that has an autonomous function alternation mechanism among sensor nodes as well as ordinary wireless sensor network capabilities such as automatic network establishment. With this mechanism, we can realized self-organized and maintenance-free sensor network systems. Its applications include surveillance of disaster-hit region, and river and forest monitoring. We are developing not only sensor node hardware but also protocols equipped to the sensor node. Custom Computing is a research field to realize a dedicated hardware using programmable logic devices such as FPGAs (Field Programmable Gate Arrays) in order to solve a give problem effectively. We focused on two applications; motif search and 3D-DCT. Motif search accelerator: It is very important to detect a common motif, i.e., partial base sequence, from DNA sequences in bioinformatics research field, and some methods have been proposed. Gibbs sampling is one of the popular methods to perform it. To accelerate Gibbs sampling with a dedicated hardware, we reconsidered the way of the evaluation-value calculation part that is the performance bottleneck of Gibbs sampling, and realized a motif search accelerator on an FPGA. Array processor for 3D-DCT: Collaborated with the Distributed Parallel Processing Laboratory in the University of Aizu, a 3D array processor for 3D-DCT was designed. In addition, the prototype system was implemented using FPGAs to evaluate the feasibility of the architecture. Satoshi Nishimura: Hardware for realistic image synthesis, Computer architecture for computer graphics, Reconfigurable hardware for multimedia applications, and Realtime systems for computer music 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. Synthesis of asynchronous circuits from a behavioral model specified by C language Design of low power and low electromagnetic interference asynchronous circuits Synthesis of network-on-chip architecture from a behavioral model

Refereed Journal Papers

[miyazaki-01:2009]	R. Kawano and T. Miyazaki. Simultaneous Optimization for Dynamic Sensor Function Allocation and Effective Sensed Data Aggregation in Wireless Sensor Networks,. International Journal of Future Generation Communication and Networking (IJFGCN), 2(4):15–28, December 2009.
	This paper proposes a method to realize sensor function allocation and effective data aggregation simultaneously in wireless sensor networks. This method realizes dynamic allocation of sensor functions so as to balance the distribution of each sensor function in a target monitoring area. In addition, effective data aggregation is performed by using a tree network topology and time division multiple access (TDMA), which is a collisionfree communication scheme. By comparing the results from the proposed method with the results from non-optimized methods, it can be validated that the proposed method is 1.7 times more efficient than non-optimized methods in distributing sensor functions. With this method, the network lifetime is doubled, and the number of data packets received at a base station is considerably increased by avoiding packet collisions.
[miyazaki-02:2009]	S. Sedukhin, T. Miyazaki, and K. Kuroda. Orbital Systolic Algorithms and Array Processors for Solution of the Algebraic Path Problem. IEICE Trans. on Information and Systems, E93-D(3):537–541, March 2010.
	The algebraic path problem (APP) is a general framework which unifies several solution procedures for a number of well-known matrix and graph problems. In this paper, we present a new 3-dimensional (3-D) orbital algebraic path algorithm and corresponding 2-D toroidal array processors which solve the n x n APP in the theoretically minimal number of 3n time-steps. The coordinated time-space scheduling of the computing and data movement in this 3-D algorithm is based on the modular function which preserves the main technological advantages of systolic processing: simplicity, regularity, locality of communications, pipelining, etc. Our design of the 2-D systolic array processors is based on a classical 3-D -¿ 2-D space transformation. We have also shown how a data manipulation (copying and alignment) can be effectively implemented in these array processors in a massively-parallel fashion by using a matrix-matrix multiply-add operation.

Refereed Proceeding Papers

[miyazaki-03:2009]	R. Kawano and T. Miyazaki. Effective Sensing Function Allocation Using a Distributed Graph Coloring and a Slot Allocation Algorithm in Wireless Sensor Networks. In Proc. The IEEE 23rd International Conference on Advanced Information Networking and Applications (AINA-09), pages 906– 913, May 2009.
	In this paper, we propose a sensing function allocation method that is based on a distributed graph coloring and a slot allocation algorithm. By using this method, a dynamic function allocation can be carried out in order to balance the distribution of each sensing function in a target monitoring area. The experimental results show that the proposed algorithm can allocate sensing functions such that 92the target monitoring area is covered and the actual sensing time is reduced by approximately 57
[miyazaki-04:2009]	S. Sedukhin and T. Miyazaki. Rapid*Closure: Algebraic Extensions of a Scalar Multiply-add Operation. In ISCA 25th International Conference on Computers and Their Applications (ISBN: 978-1-880843-75-8), pages 19– 24, March 2010.
	One of the outstanding characteristics of scalar fused multiply-add (FMA) and multiply-accumulate (MAC) operations is in reducing twice the number of required operations of an (n × n) matrix-matrix multiplication – from 2n3 multiplications and additions to exactly n3 scalar FMA/MAC operations. The existing advanced processors with FMA/MAC units are greatly reduce the time of solution of many scientific, engineering, and multimedia problems which are based on linear algebra (matrix) transforms. In this paper we show that there are other forms of matrixmatrix multiply-add in different algebraic semirings which are intensively used in many other than linear algebra real-world problems. These problems suffer from the absence of a corresponding hardware support and exhibit a relatively low speed of computing due to introducing one or two logical (branching) operations in the underline kernels. The propo sed fusion of scalar multiply-add operations for different semirings will eliminate branching and lead to an equal performance as for linear algebra. The implementation of suggested fused operations is simple and will only slightly increase the complexity of a conventional FMA/MAC unit. Our experiments on the Sony/Toshiba/IBM Cell/B.E. processor demonstrate that adding the algebraic multiply-add scalar extensions to existing FMA unit can remarkably (3× ∼ 4×) increase performance of many important problems.
[miyazaki-05:2009]	Y. Ikegaki, N. Takeishi, T. Miyazaki, and S. Sedukhin. Effective 3DDCT Calculation Based on a 3D Array Processor. In IPSJ/IEICE Forum on Information Technology 2009 (FIT2009), pages RC–004, September 2009.
	Traditional array processors randomly access to input/coefficient data stored in memory many times during the three dimensional discrete cosine transform (3D-DCT) calculation. Hence, it becomes a bottleneck of fast calculation. In this paper, a three dimensional array processor dedicated to 3D-DCT is proposed. The array processor tremendously reduces the data swapping or replacement during the calculation. Thus, it contributes to the performance improvement. The computational complexity of the proposed array processor is O(N) for an N × N × N input data cube while that of the 3D-DCT direct calculation is O(N4). A specified I/O architecture and throughput/cost-effective architectures are also discussed for practical implementation. Experimental results of an FPGA (Field Programmable Gate Array) implementation show that our architecture is not only low-power consumption but cost effective.
[miyazaki-06:2009]	R. Kawano and T. Miyazaki. Dual Optimization of Dynamic Sensor Function Allocation and Effective Sensed Data Aggregation in Wireless Sensor Networks. In Proc. International Conference on Future Generation Communication and Networking (FGCN2009) (Springer LNCS 5899), pages 255–268, July 2009.
	This paper proposes a method for dual optimization of sensor function allocation and effective data aggregation in wireless sensor networks. This method realizes dynamic allocation of sensor functions so as to balance the distribution of each sensor function in a target monitoring area. In addition, effective data aggregation is performed by using a tree network topology and time division multiple access (TDMA), which is a collision-free communication scheme. By comparing the results from the proposed method with the results from non-optimized methods, it can be validated that the proposed method is more effective. The proposed method is 1.7 times more efficient than non-optimized methods in distributing sensor functions. With this method, the network lifetime is doubled, and the number of data packets received at a base station (BS) is considerably increased by avoiding packet collisions.

Unrefereed Papers

[hiroshis-01:2009]
	H. Saito, T. Yoneda, and T. Nanya. Evaluation of a Delay Adjustment Method for FPGA Implementation of Asynchronous Circuits with Bundleddata Implementation. In 22th Karuizawa Workshop, pages 201–206, 2009.
[hiroshis-02:2009]
	H. Saito, N. Hamada, T. Yoneda, and T. Nanya. A Study of Floorplanning for Asynchronous Circuits with Bundled-data Implementation on FPGAs. In Design Gaia, 2009.
[hiroshis-03:2009]
	H Saito. Techniques for Asynchronous Circuit Design. In IEICE Fundamental Review, pages 64–70, 2010.
[miyazaki-07:2009]
	D. Shitara and T. Miyazaki. Function Alternation Algorithm in Wireless Sensor Networks. In IEICE Society Conference, volume B-7-31, September 2009.
[miyazaki-08:2009]
	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-09- 260, June 2009.
[miyazaki-09:2009]
	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-10:2009]
	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-11:2009]
	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-12:2009]
	Y. Tanno and T. Miyazaki. Evaluations of Negotiation-based Multisink Data Transfer Protocol. In IEICE General Conference, volume B-20-20, March 2010.
[miyazaki-13:2009]
	Y. Endo and T. Miyazaki. Iterative Maximum Likelihood Localization for Wireless Sensor Nodes. In IEICE General Conference, volume B-20-45, March 2010.
[miyazaki-14:2009]
	D. Shitara and T. Miyazaki. An Algorithm for Multiple Sensing- Function Alternations among Neighboring Sensor Nodes. In IEICE General Conference, volume B-20-2, March 2010.
[miyazaki-15:2009]
	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:2009]
	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.

Ciapters in Book

[miyazaki-17:2009]
	T. Miyazaki. Dynamic Sensing Function Allocation in Wireless Sensor Networks, pages 40–48. Number 64 in TELECOM FRONTIER. SCAT (Support Center for Advanced Telecommunications Technology Research), Tokyo, 2009.

Grants

[hiroshis-04:2009]	H. Saito. Ministry of Education Scientific Research Fund, 2009-2011.
[hiroshis-05:2009]	T. Yoneda, M. Imai, A. Matsumoto, and H. Saito. Core Research for Evolutional Science and Technology of Japan Science and Technology Corporation, 2008-2013.

Academic Activities

[hiroshis-06:2009]	H Saito, 2009. Associate Editor, IPSJ Transactions on System LSI Design Methodology
[hiroshis-07:2009]	H Saito, 2009. Councilor, IPSJ Tohoku Branch
[hiroshis-08:2009]	H Saito, Oct. 2009. Technical Program Committee, 4th International Symposium on Embedded Multicore Systems-on-Chip
[miyazaki-18:2009]	T. Miyazaki, 2009. Steering committee member, Technical Group for Reconfigurable Systems, IEICE
[miyazaki-19:2009]	T. Miyazaki, 2009. Steering Committee Member, CIT2009 (9th International Conference on Computer and Information Technology)
[miyazaki-20:2009]	T. Miyazaki, 2009. Technical Program Committee Member, UUWSN2009 (The International Workshop on Ubiquitous UnderWater Sensor Network 2009)
[miyazaki-21:2009]	T. Miyazaki, 2009. Technical Program Committee Member, MCSoC-09 (IEEE 4th International Symposium on Embedded Multicore Systems-on-Chip)
[miyazaki-22:2009]	T. Miyazaki, 2009. Member, IEICE
[miyazaki-23:2009]	T. Miyazaki, 2009. Member, IPSJ
[miyazaki-24:2009]	T. Miyazaki, 2009. Reviewer, The IEICE Transactions
[miyazaki-25:2009]	T. Miyazaki, 2009. Technical Program Committee Member, COOLChips (IEEE Symposium on Low- Power and High-Speed Chips)
[miyazaki-26:2009]	T. Miyazaki, 2009. Member, IEEE (CAS, ComSoc, CS)
[nisim-01:2009]	Satshi Nishimura, 2009. FAN2009/IWAC2009 organizing committee member, Japan Society for Fuzzy Theory and Intelligent Informatics

Ph.D, Master and Bachelor Theses

[hiroshis-09:2009]	Hikaru Matsuura. Graduation Thesis: Modeling of Asynchronous MIPS Processor using Haste Language, University of Aizu, 2009. Thesis Advisor: H. Saito
[hiroshis-10:2009]	Hiroyuki Shimizu. Master Thesis: Design and Evaluation of Synchronous Network-on-Chip Architecture and GALS Network-on-chip Architecture, University of Aizu, 2009. Thesis Advisor: H. Saito
[hiroshis-11:2009]	Atsunori Hirosawa. Graduation Thesis: Translation of C Language into Haste Language, University of Aizu., 2009. Thesis Advisor: H. Saito
[hiroshis-12:2009]	Daisuke Yoshida. Graduation Thesis: Visualization of Behavioral Synthesis for Asynchronous Circuits with Bundled-data Implementation, University of Aizu., 2009. Thesis Advisor: H. Saito
[hiroshis-13:2009]	Yuya Furukawa. Master Thesis: Design and Evaluation of Asynchronous AVR Microcontroller, University of Aizu, 2009. Thesis Advisor: H. Saito
[hiroshis-14:2009]	Kosuke Hirata. Master Thesis: A Behavioral Synthesis Method of Asynchronous Circuits with Bundled-data Implementation for a Behavioral Description including Floating Point Operations, University of Aizu, 2009. Thesis Advisor: H. Saito
[hiroshis-15:2009]	Yuta Horizoe. Master Thesis: A Behavioral Synthesis Method of Asynchronous Circuits with Bundled-data Implementation for a Behavioral Description including Arrays, University of Aizu, 2009. Thesis Advisor: H. Saito
[hiroshis-16:2009]	Atsunori Hirosawa. Graduation Thesis: Translation of C Language into Haste Language, University of Aizu., 2009. Thesis Advisor: H. Saito
[hiroshis-17:2009]	Hiroto Ida. Graduation Thesis: Translation of Single-rail Circuits into Dual-rail Asynchronous Circuits, University of Aizu., 2009. Thesis Advisor: H. Saito
[miyazaki-27:2009]	Masatoshi Nakano. Graduation Thesis: Human Position Estimation Using Infrared Sensors, University of Aizu, 2009. Thesis Advisor: T. Miyazaki
[miyazaki-28:2009]	Hiroyuki Igarashi. Graduation Thesis: Implementation and Evaluation of Dedicated I/O Interface for 3D Array Processor, University of Aizu, 2009. Thesis Advisor: T. Miyazaki
[miyazaki-29:2009]	Junko Tazawa. Graduation Thesis: Hardware Architecture Performing High-speed Gibbs Sampling and its FPGA Implementation, University of Aizu, 2009. Thesis Advisor: T. Miyazaki
[miyazaki-30:2009]	Yuji Endo. Master Thesis: An Iterative Multi-Lateration Based on Statistics for Wireless Sensor Networks, University of Aizu, 2009. Thesis Advisor: T. Miyazaki
[miyazaki-31:2009]	Daiki Shitara. Master Thesis: A Distributed Algorithm for Sensing- Function Alternation among Neighboring Sensor Nodes, University of Aizu, 2009. Thesis Advisor: T. Miyazaki
[nisim-02:2009]	Yu Kusaka. Graduation thesis: A Vowel Adjustment System, University of Aizu, 2010. Thesis Advisor: S. Nishimura
[nisim-03:2009]	Hironori Nishiwaki. Graduation thesis: Finger recognition with markers in OpenCV, University of Aizu, 2010. Thesis Advisor: S. Nishimura
[nisim-04:2009]	Madoka Imaizumi. Graduation thesis: Score Following Using HMM for Automatic Accompaniment, University of Aizu, 2010. Thesis Advisor: S. Nishimura
[nisim-05:2009]	Mitsuya Watanabe. Graduation thesis: Implementation of a Shading Unit for Real-Time Ray Tracing, University of Aizu, 2010. Thesis Advisor: S. Nishimura
[nisim-06:2009]	Yosuke Takahashi. Graduation thesis: A Multi-View Video Compression Method Using H.264, University of Aizu, 2010. Thesis Advisor: S. Nishimura
[nisim-07:2009]	Masuo Maekawa. Master thesis: A Case-Based Performance Rendering System Using Variable-Length Segments for Expressive Music, University of Aizu, 2010. Thesis Advisor: S. Nishimura
[nisim-08:2009]	Hiroki Matsuura. Master thesis: Optimization of Marker-based Augmented Reality with Adaptive Filters, University of Aizu, 2010. Thesis Advisor: S. Nishimura

Others

[miyazaki-32:2009]	T. Miyazaki. Newspaper article, ’KENKYU NOTE HAIKEN’, KAHOKU SHINPO, June 9, 2009(in Japanese)
[miyazaki-33:2009]	T. Miyazaki. Newspaper article, ’TOUKAIGENBA DENO KYUUJYO KATSUDOU NI HITOYAKU’FUKUSHIMA MINYU, Feb. 20, 2010 (in Japanese)
[miyazaki-34:2009]	T. Miyazaki. Magazine article, ’Die-hard Sensor Network’, in ’FUKUSHIMA-NO-SHINRO’ Fukushima Economic Research Institute, No. 327, pp. 24-27, November 2009 (in Japanese)
[nisim-09:2009]	Satoshi Nishimura. Parallel computation of PSM using GPGPU – in the case of one-dimensional Possion equation –, June 2009. presentation at the 2009-1nd PSM research meeting
[nisim-10:2009]	Satoshi Nishimura. Two-dimensional Poisson equation solver using hierarchical grid decomposition, October 2009. presentation at the 2009-2nd PSM research meeting

2011 THE UNIVERSITY OF AIZU ALL RIGHTS RESERVED