


 Department of Computer Software 
 Operating Systems Laboratory 

 
 Minyi Guo Associate Professor 

 Operating Systems Laboratory mainly researches in the following areas:
 Automatic parallelization of irregular scientific computing
 OS kernel/Compiler Integration on MIPS processor
 Operating system for embedded system and realtime systems.
 Solving NPcomplete problem using DNA computing
 Grid Computing

 Automatic parallelization of irregular scientific computing
Irregular problems arise in computational fluid dynamics, image processing, molecular dynamics simulations, galaxy simulations, climate modeling, optimization problems, and so forth. In this research, we focused on the optimization techniques of parallelism detection and implementation on compiletime for irregular problems. We used special techniques of data dependence analysis, loop transformation, data distribution for sparse matrix, communication set generation and interprocedural analysis.

 OS kernel/Compiler Integration on MIPS processor Irregular problems arise in computational fluid dynamics, image processing, molecular dynamics simulations, galaxy simulations, climate modeling, optimization problems, and so forth. In this research, we focused on the optimization techniques of parallelism detection and implementation on compiletime for irregular problems. We used special techniques of data dependence analysis, loop transformation, data distribution for sparse matrix, communication set generation and interprocedural analysis.

 Operating system for embedded system and real time systems Embedded systems are dedicated to specific tasks, which are widely used in cellular phone, domestic appliances and other electric. If an embedded system is using an operating system at all, it is most likely using a realtime operating system (RTOS), rather than Windows, Unix, Solaris, because embedded systems have power constraints and far fewer system resources than desktop systems, and so forth. This year (2003) we have studied an OS kernel for MIPS processor model. This project is support by 2003 University of Aizu Competitive Research Funding.

 Solving NPcomplete problem using DNA computing Nowadays, producing roughly 10 8DNA strands that fit in a test tube is possible through advances in molecular biology. Adleman proposed the first paper in which it is shown that each DNA strand (Deoxyribo Nucleic Acid) could be employed towards calculating solutions to an instance of the NPcomplete Hamiltonian path problem (HPP) with seven vertices. Lipton demonstrated that using Adleman's experiment determines solutions to an instance of the NPcomplete satisfiability (SAT) problem. Therefore, the AdlemanLipton model seems to be another selection of solving NPcomplete problem. In this research, we focused on developing DNA algorithms in the AdlemanLipton model for resolving 3DIMENSIONAL MATCHING (3DM), and MINIMUMSETCOVER (transformation from 3DM). Also we focused on developing simulator to simulate real DNA experiment of the proposed algorithms.

 Grid Computing The grid is an emerging infrastructure that will fundamentally change the way we think about  and use  computing. The grid will connect multiple regional and national computational grids to create a universal source of computing power. A Grid is a computing and data handling virtual system formed by aggregating the diverse services provided by distributed resources to synthesize problem solving environments. Some of the issues in Grid architecture are: (a) supporting adaptability, extensibility, and scalability, (b) allowing systems with different administrative policies to interoperate while preserving site autonomy, (c) coallocating resources, and (d) supporting quality of service. In Operating Systems Lab., we have develop a project which studies a novel, highly decentralized, Grid OS architecture that borrows features from Internet routing architectures. Our Grid OS design includes several novel ideas including
 a flexible naming scheme,
 a service mobility protocol, and
 a highly decentralized Grid scheduling mechanism.
The naming scheme supports aggregation of resource names based on attributes. In our architecture, the Grid OS runs on each node that participates in the Grid. Therefore, it is essential that the Grid OS is lightweight so that the overhead is minimal and at the same time powerful enough to support different services. Our Grid OS provides a service mobility protocol to migrate/replicate services depending on the demand.



 [minyi01:2003]  Yi Pan, Joseph J.S. Shang, and Minyi Guo. A Scalable HPF Implementation of Finite VolumeCEM Application on a Cray T3E Parallel System. Concurrency and Computation: Practice an Experience, 15(6):607621, 2003.
In this paper, we discuss aneAEcientandscalable parallelizationof thesequential Fortran timedependentMaxwell equations solver using High Performance Fortran (HPF). The background of the project, the theory behind the eAEciency being achieved, the parallelization methodologies employed, and the experimental results obtained on the CrayT3E massively parallel computing system will be described in detail. Experimental runs show that the execution time is reduced drastically through parallel computing. The code is scalable up to 98 processors on the CrayT3Eandhas a similar performance comparedto an MPI implementation. Based on the experimentation carried out in this research, we believe that a high level parallel programming language such as High Performance Fortran is a fast, viable and economical approach to parallelizing many existing sequential codes which exhibit a lot of parallelism. 
 [minyi02:2003]  WengLong Chang, Michael Ho, and Minyi Guo. Molecular Solutions for Subset Problem on DNAbased Supercomputing. BioSystems, 73(2):117130, 2004.
In this paper our main purpose is to give molecular solutions for the subsetsum problem. In order to achieve this, we propose a DNAbased algorithm of an nbit parallel adder and a DNAbased algorithm of an nbit parallel comparator to formally verify our designed molecular solutions for the subsetsum problem. 
 [minyi03:2003]  Laurence T. Yang, Yi Pan, and Minyi Guo. Parallel and Distributed Scientific and Engineering Computing. Parallel Computing, 29(11):15051508, 2003.
In this paper, we give an overview of the recent important advances in the area of parallel and distributed scientific and engineering computing. We introduce some recent achievements in the scientific and engineering computing domains 
 [minyi04:2003]  WengLong Chang and Minyi Guo. Solving the Set Cover Problem and the Problem of Exact Cover By3Sets in the AdlemanLipton Model. Bio Systems, 72(3):263275, 2003.
Adleman wrote the first paper in which it is shown that DNA(DeoxyriboNucleic Acid) strands could be employed towards calculating solutions to an instance of the NPcomplete Hamiltonian path problem (HPP). Lipton also demonstrated that applying Adleman's techniques could be used to solve the NPcomplete satisfiability (SAT) problem (the first NPcomplete problem). In this paper, it is proved how the DNA operations presented by Adleman and Lipton can be used for developing DNA algorithms to resolving the set cover problem and the problem of exact cover by 3sets. 
 [minyi05:2003]  Minyi Guo. EAEcient LoopPartitioning for Parallel Codes of Irregular Scientific Computations. IEICE Transactions on Information and Systems, E86D(9):18251834, 2003.
In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. We partition a loop iteration to a processor on which the minimal communication cost is ensured when executing that iteration. Then, after all iterations are partitioned into various processors, we give global vs. local data transformation rule, indirection arrays remapping and communication optimization methods. 
 [minyi06:2003]  Minyi Guo, Yi Pan, and Zhen Liu. Symbolic Communication Set Generation for Irregular Parallel Applications. The Journal of Super comuputing, 25(3):199214, 2003.
In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. We partition a loop iteration to a processor on which the minimal communication cost is ensured when executing that iteration. Then, after all iterations are partitioned into various processors, we give global vs. local data transformation rule, indirection arrays remapping and communication optimization methods. 

 Refereed Proceeding Papers 

 [minyi07:2003]  Zhen Liu and Minyi Guo. Is Cook's Theorem Correct for DNAbased Computing  Towards Solving the NPComplete Problems on a DNAbased Supercomputer Model. In Proceedings of 5th International Symposium on High Performance Computing (ISHPCV), Tokyo, Japan, October 2003.
Lecture Notes in Computer Science 2858

 [minyi08:2003]  WengLong Chang, Minyi Guo, and Machael Ho. Solving the Setbasis Problem in Stickerbased Model and the AdlemanLipton Model. In the 5th International Workshop on High Performance Scientific and Engineering computing with Applications (HPSECA2003), pages 455 460, Kaohsiung, Taiwan, October 2003. IEEE Computer Society Press.
In conjunction with International Conference ICPP 2003

 [minyi09:2003]  Hui Wang, Minyi Guo, and Yi Pan. Parallelization of High Order MultiDomain PADE Solver FDL2DICE. In the 2th International Workshop on Hardware/Software Support for High Performance Scientific and Engineering computing (SHPSEC2003), New Orleans, USA, September 27  October 1, 2003, New Orleans, USA, September 2003. ACM, ACM Press.
In conjunction with International Conference PACT 2003

 [minyi10:2003]  WengLong Chang and Minyi Guo. Molecular DNAbased Solution For SetPacking and Clique Problems. In the 2th International Workshop on Hardware/Software Support for High Performance Scientific and Engineering computing (SHPSEC2003), New Orleans, USA, September 27  October 1, 2003, New Orleans, USA, September 2003. ACM, ACM Press.
In conjunction with International Conference PACT 2003

 [minyi11:2003]  Hui Wang, Minyi Guo, Sushil K. Prasad, Yi Pan, and Wenxi Chen. An EAEcient Algorithm for Irregular Redistributions in Parallelizing Compilers. In Minyi Guo and Laurence T. Yang, editors, Proceedings of ISPA03, AizuWakamatsu City, July 2003, pages 76{87, Aizu Wakamatsu, July 2003. Univ. of Aizu.
Lecture Notes in Computer Science 2745

 [minyi12:2003]  Zhen Liu, Shin'ichi Kamohara, and Minyi Guo. A Scheme of Interactive Data Mining Support System in Parallel and Distributed Environment. In Minyi Guo and Laurence T. Yang, editors, Proceedings of ISPA03, AizuWakamatsu City, July 2003, pages 263{272, Aizu Wakamatsu, July 2003. Univ. of Aizu.
Lecture Notes in Computer Science 2745

 [minyi13:2003]  WengLong Chang, Minyi Guo, and Michael Ho. Solving the Setsplitting Problem in Stickerbased Model and the AdlemanLipton Model. In Minyi Guo and Laurence T. Yang, editors, Proceedings of ISPA03, AizuWakamatsu City, July 2003, pages 185196, Aizu Wakamatsu, July 2003. Univ. of Aizu.
Lecture Notes in Computer Science 2745



 [minyi14:2003]  Minyi Guo and Laurence T. Yang. Parallel and Distributed Computing with Applications. Number 2745 in Lecture Notes in Computer Science. SpringerVerlag, Berlin, 2003.



 [minyi15:2003]  Minyi Guo. Automatic Parallelization and Optimizations for Irregular Applications, Ministry of Education GrantinAid: Basic Research (C), Contract No. 14580386, 20022003.



 [minyi16:2003]  Minyi Guo, 2002.
IEIC member

 [minyi17:2003]  Minyi Guo, 2002.
IEEE, IEEE Computer Society member

 [minyi18:2003]  Minyi Guo, 2002.
ACM member

 [minyi19:2003]  Minyi Guo, 2002.
IPSJ member

 [minyi20:2003]  Minyi Guo, July 2003.
Program Committee Chair, The2003International Symposium on Parallel and Distributed Computing with Applications (ISPA2003). 
 [minyi21:2003]  Minyi Guo, September 2003.
Program Committee Chair, the 2nd International Workshop on Hardware/Software Support for Parallel and Distributed Scientific and Engineering Computing (PACTSPDSEC03). 
 [minyi22:2003]  Minyi Guo, March 2004.
Workshop Chair, the 1st International Workshop on Embedded Computing (ICDCSEC04). 
 [minyi23:2003]  Minyi Guo, August 2004.
Program Committee member, The 4th Workshop on High Performance Scientific and Engineering Computing with Applications (HPSECA03). 
 [minyi24:2003]  Minyi Guo, December 2003.
Program Committee member, The International Workshop on Grid and Cooperative Computing (GCC 2003) 


 [minyi25:2003]  Yoshiaki Takagi. Graduation Thesis: Task scheduling evaluation effect on overhead time in embedded systems, University of Aizu, 2003.
Thesis Advisor: Minyi Guo.

 [minyi26:2003]  Kazuhiko Yagyu. Graduation Thesis: Evaluation of the Global Computing Environment Using Globus Toolkit, University of Aizu, 2003.
Thesis Advisor: Minyi Guo.

 [minyi27:2003]  Hisamitsu Sato. Graduation Thesis: Development of a Data Dependence Visualization Tool, University of Aizu, 2003.
Thesis Advisor: Minyi Guo.

 [minyi28:2003]  Kazuhiko Yagyu. Graduation Thesis: High performance peertopeer matrix multiplication by using JXTA, University of Aizu, 2003.
Thesis Advisor: Minyi Guo.

 [minyi29:2003]  Naoto Suzuki. Graduation Thesis: Development of a real time OS in a cellular phone emulator, University of Aizu, 2003.
Thesis Advisor: Minyi Guo.

