Computer Organization Laboratory

Tosiaki Miyazaki Professor	Satoshi Nishimura Associate Professor	Hiroshi Saito Assistant Professor	Wanming Chu Assistant Lecturer	V. B. Marakhovsky Visiting Professor

The following researches are progressed in Computer Organization Laboratory: Toshiaki Miyazaki: Die-hard sensor network Related to this topic, the following six items were done in 2007. Network technology: To establish a wireless network among all nodes, we proposed a two-layered network structure, and developed two different types of nodes for it; base stations (BSs) and sensor nodes (SNs). BSs are used to aggregate the sensed data coming from SNs, while SNs are in charge of environment sensing. In the network for BSs, IEEE 802.11b, a standardized WLAN, with AODV (Ad hoc On-Demand Distance Vector) routing protocol are used because they are well-studied, stable, and inexpensive. On the other hand, in the sensor network layer, we have to manage many sensor nodes. Thus, to avoid complicated operations such as IP address handling, we introduced an original protocol based on ZigBee. The network works as we designed. However, it is still needed an enhancement to improve its reliability. It is one of our R & D issues in the next year. Location estimation of sensor nodes: The sensor nodes are often deployed to under debris, so they cannot know their own locations directly using the GPS. Thus, a method is needed to estimate the location of each sensor node from the known locations of the BSs having GPS receivers. We developed a new algorithm that can estimate the locations of all sensor nodes from some BSs whose locations are known, as the anchors. It is based on the three-point measurement method, but a dynamic enhancement scheme that can improve the estimation quality of the node locations is featured in the basic algorithm. Our algorithm can estimate the location of a sensor node with 3.28m error on average. The result is about 6 Data aggregation and display: These functions should be realized in the observers terminal. We developed its initial version. Although the software only has the overview display function, it is useful for the users to understand the situations of the observing field. Sensor node design: At the beginning, we planned to develop an original sensor module. However, based on the preliminary experiment for the wireless communication among the sensor nodes, the communication was not stable, and we recognized that the development of a stable sensor network is more important issue than that of the sensor module. Thus, we concentrated on it, and developed a protocol utilizing multi-hop and multi-sink communications. The developed protocol is deployed as a part of the network technology shown in item (a). Function alternation mechanism: An algorithm that can distribute a software program to many sensor nodes using the wireless communications is developed. This is useful when we want to deliver a new program to all sensor nodes quickly. System integration: In addition to developing above-mentioned fundamental mechanisms, we developed a pre-prototype system by integrating them and conrmed each basic mechanism performs as expected. Hardware design for an scalable array processor Collaborated with the Operating System Laboratory in the University of Aizu, the hardware architecture of the scalable array processor dedicated to high-speed matrix-matrix operations was designed. In addition, the prototype system was implemented using FPGAs (Field Programmable Gate Arrays) 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: We are developing a behavioral synthesis tool for asynchronous circuits with bundleddata implementation. From a behavioral description specied by a sub-set of C language, the developed tool synthesized area or performance optimum bundled-data implementation. The main achievements of 2007 are: Extension of the sub-set of C language Implementation of bit-width analysis and optimization A delay adjustment method targeting FPGA implementation Wanming Chu: Parallel multithreaded processor architecture. Visual simulator for MIPS processor. The algorithms for interconnection networks.

Refereed Journal Papers

[hiroshis-01:2007]	H. Saito, N. Hamada, N. Jindapetch, T. Yoneda, C. Myers, and T. Nanya. Scheduling Methods for Asynchronous Circuits with Bundled-Data Implementations Based on the Approximation of Start Times. IEICE Trans- actions, E90-A(12):2790-2799, 2007.
	This paper proposes new scheduling methods for asynchronous circuits with bundleddata implementations. Since operations in asynchronous circuits start after the completion of a previous operation, this method approximates the set of start times for each operation using the delay of the resources. Next, this method decides on control steps from the approximated sets of start times, which are used in scheduling algorithms. This paper extends two scheduling algorithms used for synchronous circuits so that the approximated sets of start times and the decided control steps are used. Finally, this paper shows the effectiveness of our proposed methods by comparing scheduling results with ones obtained by the original two scheduling algorithms.
[miyazaki-01:2007]	Y. Nomoto, Y. Sato, and T. Miyazaki. An effective data I/O mechanism utilizing FIFOs for an array processor. Proc. IEICE Technical Committee on Recongurable Systems (RECONF), RECONF2007-70, Jan. 2008.
	Data I/O management is very important to handle huge data effectively in signal and image processing with array processors. In this paper, we propose an effective data I/O architecture utilizing FIFOs tuned to an array processor. Several FIFOs are provided to store initial matrix data and partially processed results. By switching the FIFOs promptly and transferring data from (to) them to (from) the array processor, we can eliminate the data transfer itself between the external memory and the array processor, which often becomes a performance bottle-neck of array processors, and improve the I/O throughputs.

Refereed Proceeding Papers

[hiroshis-02:2007]	T. Konishi, N. Hamada, and H. Saito. A Control Circuit Synthesis Method for Asynchronous Circuits in Bundled-Data Implementation. In Inter- national Conference on Compute and Information Technology, pages 847-852. IEEE, Oct. 2007.
	This paper proposes a control circuit synthesis method for asynchronous circuits in bundled-data implementation. Our proposed method consists of the synthesis of a control circuit to control a data-path circuit and the synthesis of an interface circuit between the control circuit and the data-path circuit. The control circuit is generated by mapping small control elements called Q-elements. For mapping, this paper proposes two mapping methods called the state-oriented mapping method and the node-oriented mapping method. Finally, this paper shows the effectiveness of the proposed method by comparing synthesized circuits with ones obtained by a different control circuit synthesis method.
[miyazaki-02:2007]	R. Kawano and T. Miyazaki. Distributed Coloring Algorithm for Wireless Sensor Networks and Its Applications. In Proc. IEEE 7th International Conference on Computer and Information Technology (CIT2007), pages 997-1002, Oct. 2007.
	In this paper, we propose a distributed coloring algorithm that is commonly applicable to many optimization problems to realize wireless sensor networks (WSNs). After describing the algorithm in detail, two applications, namely sensing function allocation and time-slot allocation in the time division multiple access (TDMA) communication, are introduced. The experimental results for the applications show that the proposed algorithm effectively solves the problems in the applications.
[miyazaki-03:2007]	R. Fujita T. Miyazaki T. Hayashi, H. Fukuhara and S. Saito. A Messaging Network to Realize an SOA-based System. In Proc. IEEE 7th International Conference on Computer and Information Technology (CIT2007), pages 1083-1088, Oct. 2007.
	This present paper introduces an approach to construct an SOA-based system using a messaging network. The proposed solution uses a messaging networking, which is a type of overlay networking. The proposed approach can reduce the complexity and the maintenance cost of the system, which both makes an information system vulnerable. Therefore, the proposed approach can contribute to the construction of a secure information system. The requirements of a messaging network for an SOA-based system are presented.
[miyazaki-04:2007]	K. Onodera and T. Miyazaki. An Autonomous Multicast-tree Creation Algorithm for Wireless Sensor Networks. In Proc. 2007 Inter- national Conference on Future Generation Communication and Networking (FGCN2007), pages 267-272, Dec. 2007.
	In this paper, we propose an algorithm to realize a power-aware network topology in wireless sensor networks. The algorithm creates a multicast tree connecting all sensor nodes. In the multicast tree, a sink node should be a root node, and all the data sensed in the sensor nodes are transferred to the sink node using the tree connection. The relay nodes aggregate the received data, and transfer the aggregated data to the sink at an appropriate timing so as to avoid packet collisions. To do this, all the sensor nodes are grouped in clusters. Here, each cluster has a head node, which is automatically selected from among the nodes in the cluster. In addition, our algorithm has an autonomous mechanism that can change the cluster head dynamically based on the remaining energy of each sensor node and the communication quality among the sensor nodes, which are obtained by periodical information exchange between the sensor nodes. This mechanism contributes to extending the lifetime of the sensor network. After describing the algorithm, some experimental results are shown to prove its effectiveness and robustness.
[miyazaki-05:2007]	K. Onodera and T. Miyazaki. An Autonomous Algorithm for Construction of Energy-conscious Communication Tree in Wireless Sensor Networks. In Proc. The Fourth IEEE International Workshop on Heterogeneous Wireless Networks (HWISE2008) in AINA2008, pages 898-903, March 2008.
	In wireless sensor networks, it is useful to construct a tree communication network topology in order to effectively collect sensed data from sensor nodes at a sink node. In the tree, the sink node should be a root node, and all the data sensed in the sensor nodes are transferred to the sink node using the tree connections. Compared to other topologies such as the mesh and random topologies, the tree topology does not request any routing protocols because each route from a sensor node to the sink node is uniquely decided after the tree structure is constructed. In this paper, we propose an autonomous algorithm for tree creation and its maintenance. It can extend the lifetime of the sensor network and support efficient data aggregation by balancing the communication tree structure automatically. Moreover, our algorithm simply manages all the involved sensor nodes and creates a tree structure by using them. Thus, this algorithm can be applied to actual sensor networks along with other algorithms or protocols. After describing the algorithm, some experimental results are shown to prove its effectiveness and robustness.
[miyazaki-06:2007]	R. Kawano and T. Miyazaki. Distributed Data Aggregation in Multi-sink Sensor Networks using a Graph Coloring Algorithm. In Proc. The Fourth IEEE International Workshop on Heterogeneous Wireless Networks (HWISE2008) in AINA2008, pages 934-940, March 2008.
	In this paper, we propose an algorithm to minimize the multihop route from each sensor node to a sink node in wireless sensor networks with multiple sink nodes. In addition to solving the shortest path problem, the algorithm solves a time slot problem to support TDMA (time division multiple access) communication. TDMA is effective for avoiding packet collisions; however, the time slot allocation itself is a difficult problem to solve. We introduce a distributed coloring algorithm to solve it. After describing the algorithm, some experimental results proving its effectiveness are presented.
[w-chu-01:2007]	Yamin Li, Shietung Peng, and Wanming Chu. An Algorithm for Constructing Hamiltonian Cycle in Metacube Networks. In David S. Munro, editor, Proceedings of the International Conference on Parallel and Distributed Com- puting, Applications and Technologies (PDCAT'07), pages 285-292, Adelaide, Australi, December 2007. IEEE, IEEE Computer Society Press.
	The high-performance supercomputers will consist of several millions of CPUs in the next decade. The interconnection networks (INs) in such supercomputers play an important role. Metacube (MC) is an attractive IN that can connect extremely large number of nodes with small number of links, meanwhile it holds a short diameter and keeps the simplicity of routing algorithm. An MC(k,m) network can connect 2m2k+k nodes with m + k links per node, where k is the dimension of the high-level cubes (classes) and m is the dimension of the low-level cubes (clusters). For example, an MC(3,3) with 6 links per node can connect 227, or 134,217,728, nodes. In this paper, we show that the Metacube is Hamiltonian and give an efficient algorithm to construct a Hamiltonian cycle in Metacube networks.

Unrefereed Papers

[hiroshis-03:2007]	Y. Shiga, N. Hamada, T. Konishi, and H. Saito. Behavioral Synthesis Method for Asynchronous Circuits with Bundled-Data Implementation Considering Bit Length. In DA Symposium, pages 187-192. IPSJ, Aug. 2007.
[miyazaki-07:2007]	NK. Onodera Y. Endo, R. Kawano and T. Miyazaki. An Approach to Node Position Estimation in Real-World Wireless Sensor Network. In IPSJ 70th general conference, volume 2ZA-6, March 2008.
[miyazaki-08:2007]	R. Kawano K. Onodera and T. Miyazaki. Energy Conscious Tree Topology Creation for Wireless Sensor Networks. In IPSJ 70th general con- ference, volume 5Z-8, March 2008.
[miyazaki-09:2007]	Y. Sato, Y. Nomoto, T. Miyazaki, and S. Sedukhin. 2-D Array Processor Featuring Ternary Input Fused Operations. In IPSJ SIG Tech. Reports, volume 2007-SLDM-131-2, Oct 2007.
[miyazaki-10:2007]	K. Onodera R. Kawano and T. Miyazaki. Data Collection in Multisink Sensor Networks using a Graph Coloring Algorithm. In IPSJ 70th general conference, volume 5Z-7, March 2008.

Grants

[hiroshis-04:2007]	H. Saito. Ministry of Education Scientific Research Fund, 2006- 2008.
[miyazaki-11:2007]	T. Miyazaki. Grant from the Support Center of Advanced Telecommunications Technology Research (SCAT), 2006-2007.
[miyazaki-12:2007]	T. Miyazaki. JSPS Grant-in-Aid for Scientific Research (No. 18500060), 2006-2008.

Academic Activities

[hiroshis-05:2007]	H Saito, 2007. Committee member, IPSJ SIGSLDM
[hiroshis-06:2007]	H Saito, 2007. Committee member, IPSJ Tohoku branch
[hiroshis-07:2007]	H Saito, 2007. Associate Editor, IPSJ TSLDM
[hiroshis-08:2007]	H Saito, Oct. 2007. Organization committee member, IEEE CIT
[miyazaki-13:2007]	T. Miyazaki, June 2007. Lecturer 'FPGA technologies changing system design' in 'System LSI design technologies course', IEICE Advanced Open Lecture Series
[miyazaki-14:2007]	T. Miyazaki, 2007. Steering committee member, Technical Group for Reconfigurable Systems, IEICE
[miyazaki-15:2007]	T. Miyazaki, 2007. Technical Program Committee Member, ISVLSI2007 (IEEE International Symposium on VLSI)
[miyazaki-16:2007]	T. Miyazaki, 2007. Technical Program Committee Member, RC education 2007 (International Workshop on Reconfigurable Computing Education)
[miyazaki-17:2007]	T. Miyazaki, 2007. Technical Program Committee Member, ACST2007 (The Third IASTED International Conference on Advances in Computer Science and Technology)
[miyazaki-18:2007]	T. Miyazaki, 2007. Program Co-chair, CIT2007 (7th International Conference on Computer and Information Technology)
[miyazaki-19:2007]	T. Miyazaki, 1984 - present. Member, IEICE
[miyazaki-20:2007]	T. Miyazaki, 1986 - present. Member, IPSJ
[miyazaki-21:2007]	[miyazaki-21:2007] T. Miyazaki, 1988 - present. Member, IEEE (CAS, ComSoc, CS)
[miyazaki-22:2007]	T. Miyazaki, 2007. Reviewer, The IEICE Transactions
[miyazaki-23:2007]	T. Miyazaki, 2007. Reviewer, The Institute of Electrical Engineers of Japan

Patents

[miyazaki-24:2007]

S. Sedukhin T. Miyazaki, K. Kuroda and Y. Nomoto. Array Processor 2008-000351, Jan. 2008.

Ph.D and Others Theses

[hiroshis-09:2007]	Naohiro Hamada. Master Thesis: A Behavioral Synthesis System for Asynchronous Circuits with Bundled-data Implementation, University of Aizu, 2007. Thesis Advisor: Saito, H.
[hiroshis-10:2007]	Yuki Kunisawa. Master Thesis: A Delay Adjustment Method for Asynchronous Circuits with Bundled-data Implementation targeting at FPGA Implementation, University of Aizu, 2007. Thesis Advisor: Saito, H.
[hiroshis-11:2007]	Yusuke Nomoto. Master Thesis: QueueDoRegister: An Effective Data I/O Mechanism Utilizing FIFOs for an Array Processor, University of Aizu, 2007. Thesis Advisor: Saito, H.
[hiroshis-12:2007]	Yuya Furukawa. Graduation Thesis: An Iterative Resource Allocation Method Using the Properties of FPGAs, University of Aizu, 2007. Thesis Advisor: Saito, H.
[hiroshis-13:2007]	Yuta Horizoe. Graduation Thesis: A Behavioral Synthesis Method for Asynchronous Circuits with Bundled-data Implementations from Array Descriptions, University of Aizu, 2007. Thesis Advisor: Saito, H.
[hiroshis-14:2007]	Kosuke Hirata. Graduation Thesis: Behavioral Synthesis of Asynchronous Circuits from a Behavioral Description with Floating Point Operations, University of Aizu, 2007. Thesis Advisor: Saito, H.
[hiroshis-15:2007]	Ayumi Ito. Graduation Thesis: Force-directed List Scheduling for Asynchronous Circuits with Bundled-data Implementations, University of Aizu, 2007. Thesis Advisor: Saito, H.
[miyazaki-25:2007]	Daiki Shitara. Graduation Thesis: Dynamic Function Modification Method for Multiple Sensor Nodes in Wireless Sensor Networks, University of Aizu, 2007. Thesis Advisor: T. Miyazaki
[miyazaki-26:2007]	Manabu Otsuka. Graduation Thesis: An Implementation of I/O Interface for an Array Processor, University of Aizu, 2007. Thesis Advisor: T. Miyazaki
[miyazaki-27:2007]	Takanobu Sato. Graduation Thesis: Spatial Filtering Algorithm Dedicated to a 2D Torus Array Processor, University of Aizu, 2007. Thesis Advisor: T. Miyazaki
[miyazaki-28:2007]	Katsumi Onodera. Master Thesis: An Autonomous Maintenance Tree Construction for Wireless Sensor Network, University of Aizu, 2007. Thesis Advisor: T. Miyazaki
[miyazaki-29:2007]	Yuji Endo. Graduation Thesis: Node Localization Method in Real- World Wireless Sensor Networks, University of Aizu, 2007. Thesis Advisor: T. Miyazaki
[nisim-01:2007]	Ryota Kuroki. Graduation Thesis: Handling 3D Sound Diffraction in Path Tracing, University of Aizu, 2008. Thesis Advisor: Satoshi Nishimura
[nisim-02:2007]	Hiroki Matsuura. Graduation Thesis: Real-time Ray Tracing on a GPU System, University of Aizu, 2008. Thesis Advisor: Satoshi Nishimura
[nisim-03:2007]	Yasuhiro Sawabe. Graduation Thesis: Speed-Up of Ray Tracing Using Space Subdivision and Cell Processor, University of Aizu, 2008. Thesis Advisor: Satoshi Nishimura
[nisim-04:2007]	Eiji Tachizaki. Graduation Thesis: Musical Score Editor for the Visualization of Samuel's Description, University of Aizu, 2008. Thesis Advisor: Satoshi Nishimura
[nisim-05:2007]	Masuo Maekawa. Graduation Thesis: A Performance Position Analysis Algorithm for Automatic Accompaniment, University of Aizu, 2008. Thesis Advisor: Satoshi Nishimura

Others

[miyazaki-30:2007]

T. Miyazaki. Visiting lecturer, The Tokyo University of Agriculture and Technology

2009 THE UNIVERSITY OF AIZU ALL RIGHTS RESERVED