Japanese
Department of Computer Software

Operating Systems Laboratory

Minyi Guo
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 real-time systems.
  • Solving NP-complete 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 compile-time for irregular problems. We used special techniques of data dependence analysis, loop transformation, data distribution for sparse matrix, communication set generation and inter-procedural 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 compile-time for irregular problems. We used special techniques of data dependence analysis, loop transformation, data distribution for sparse matrix, communication set generation and inter-procedural 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 real-time 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 NP-complete 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 NP-complete Hamiltonian path problem (HPP) with seven vertices. Lipton demonstrated that using Adleman's experiment determines solutions to an instance of the NP-complete satisfiability (SAT) problem. Therefore, the Adleman-Lipton model seems to be another selection of solving NP-complete problem. In this research, we focused on developing DNA algorithms in the Adleman-Lipton model for resolving 3-DIMENSIONAL MATCHING (3DM), and MINIMUMSET-COVER (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 inter-operate 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
  1. a flexible naming scheme,
  2. a service mobility protocol, and
  3. 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.

Refereed Journal Papers

[minyi-01: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):607-621, 2003.

In this paper, we discuss aneAEcientandscalable parallelizationof thesequential Fortran time-dependentMaxwell 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.
[minyi-02:2003]Weng-Long Chang, Michael Ho, and Minyi Guo. Molecular Solutions for Sub-set Problem on DNA-based Supercomputing. BioSystems, 73(2):117-130, 2004.

In this paper our main purpose is to give molecular solutions for the subset-sum problem. In order to achieve this, we propose a DNA-based algorithm of an n-bit parallel adder and a DNA-based algorithm of an n-bit parallel comparator to formally verify our designed molecular solutions for the subset-sum problem.
[minyi-03:2003]Laurence T. Yang, Yi Pan, and Minyi Guo. Parallel and Distributed Scientific and Engineering Computing. Parallel Computing, 29(11):1505-1508, 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
[minyi-04:2003]Weng-Long Chang and Minyi Guo. Solving the Set Cover Problem and the Problem of Exact Cover By3-Sets in the Adleman-Lipton Model. Bio Systems, 72(3):263-275, 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 NP-complete Hamiltonian path problem (HPP). Lipton also demonstrated that applying Adleman's techniques could be used to solve the NP-complete satisfiability (SAT) problem (the first NP-complete 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 3-sets.
[minyi-05:2003]Minyi Guo. EAEcient LoopPartitioning for Parallel Codes of Irregular Scientific Computations. IEICE Transactions on Information and Systems, E86-D(9):1825-1834, 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.
[minyi-06:2003]Minyi Guo, Yi Pan, and Zhen Liu. Symbolic Communication Set Generation for Irregular Parallel Applications. The Journal of Super comuputing, 25(3):199-214, 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

[minyi-07:2003]Zhen Liu and Minyi Guo. Is Cook's Theorem Correct for DNA-based Computing - Towards Solving the NP-Complete Problems on a DNA-based Supercomputer Model. In Proceedings of 5th International Symposium on High Performance Computing (ISHPC-V), Tokyo, Japan, October 2003.

Lecture Notes in Computer Science 2858

[minyi-08:2003]Weng-Long Chang, Minyi Guo, and Machael Ho. Solving the Set-basis Problem in Sticker-based Model and the Adleman-Lipton Model. In the 5th International Workshop on High Performance Scientific and Engineering computing with Applications (HPSECA-2003), pages 455- 460, Kaohsiung, Taiwan, October 2003. IEEE Computer Society Press.

In conjunction with International Conference ICPP 2003

[minyi-09:2003]Hui Wang, Minyi Guo, and Yi Pan. Parallelization of High Order Multi-Domain PADE Solver FDL2DICE. In the 2th International Workshop on Hardware/Software Support for High Performance Scientific and Engineering computing (SHPSEC-2003), New Orleans, USA, September 27 - October 1, 2003, New Orleans, USA, September 2003. ACM, ACM Press.

In conjunction with International Conference PACT 2003

[minyi-10:2003]Weng-Long Chang and Minyi Guo. Molecular DNA-based Solution For Set-Packing and Clique Problems. In the 2th International Workshop on Hardware/Software Support for High Performance Scientific and Engineering computing (SHPSEC-2003), New Orleans, USA, September 27 - October 1, 2003, New Orleans, USA, September 2003. ACM, ACM Press.


In conjunction with International Conference PACT 2003
[minyi-11: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, Aizu-Wakamatsu City, July 2003, pages 76{87, Aizu Wakamatsu, July 2003. Univ. of Aizu.

Lecture Notes in Computer Science 2745

[minyi-12: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, Aizu-Wakamatsu City, July 2003, pages 263{272, Aizu Wakamatsu, July 2003. Univ. of Aizu.

Lecture Notes in Computer Science 2745

[minyi-13:2003]Weng-Long Chang, Minyi Guo, and Michael Ho. Solving the Set-splitting Problem in Sticker-based Model and the Adleman-Lipton Model. In Minyi Guo and Laurence T. Yang, editors, Proceedings of ISPA03, Aizu-Wakamatsu City, July 2003, pages 185-196, Aizu Wakamatsu, July 2003. Univ. of Aizu.

Lecture Notes in Computer Science 2745

Books

[minyi-14:2003]Minyi Guo and Laurence T. Yang. Parallel and Distributed Computing with Applications. Number 2745 in Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2003.

Grants

[minyi-15:2003]Minyi Guo. Automatic Parallelization and Optimizations for Irregular Applications, Ministry of Education Grant-in-Aid: Basic Research (C), Contract No. 14580386, 2002-2003.

Academic Activities

[minyi-16:2003]Minyi Guo, 2002.

IEIC member

[minyi-17:2003]Minyi Guo, 2002.

IEEE, IEEE Computer Society member

[minyi-18:2003]Minyi Guo, 2002.

ACM member

[minyi-19:2003]Minyi Guo, 2002.

IPSJ member

[minyi-20:2003]Minyi Guo, July 2003.

Program Committee Chair, The2003International Symposium on Parallel and Distributed Computing with Applications (ISPA2003).
[minyi-21:2003]Minyi Guo, September 2003.

Program Committee Chair, the 2nd International Workshop on Hardware/Software Support for Parallel and Distributed Scientific and Engineering Computing (PACT-SPDSEC-03).
[minyi-22:2003]Minyi Guo, March 2004.

Workshop Chair, the 1st International Workshop on Embedded Computing (ICDCS-EC04).
[minyi-23:2003]Minyi Guo, August 2004.

Program Committee member, The 4th Workshop on High Performance Scientific and Engineering Computing with Applications (HPSECA-03).
[minyi-24:2003]Minyi Guo, December 2003.

Program Committee member, The International Workshop on Grid and Cooperative Computing (GCC 2003)

Ph.D and Other Theses

[minyi-25:2003]Yoshiaki Takagi. Graduation Thesis: Task scheduling evaluation effect on overhead time in embedded systems, University of Aizu, 2003.

Thesis Advisor: Minyi Guo.

[minyi-26:2003]Kazuhiko Yagyu. Graduation Thesis: Evaluation of the Global Computing Environment Using Globus Toolkit, University of Aizu, 2003.

Thesis Advisor: Minyi Guo.

[minyi-27:2003]Hisamitsu Sato. Graduation Thesis: Development of a Data Dependence Visualization Tool, University of Aizu, 2003.

Thesis Advisor: Minyi Guo.

[minyi-28:2003]Kazuhiko Yagyu. Graduation Thesis: High performance peer-to-peer matrix multiplication by using JXTA, University of Aizu, 2003.

Thesis Advisor: Minyi Guo.

[minyi-29:2003]Naoto Suzuki. Graduation Thesis: Development of a real time OS in a cellular phone emulator, University of Aizu, 2003.

Thesis Advisor: Minyi Guo.