|
|
 |
|
|
Operating Systems Laboratory |
Minyi Guo
Assistant Professor |
Chengfei Liu
Visiting Researcher |
|
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 OS architecture for Grid Computing
Automatic parallelization of irregular scientific computing
Irregular problems arise in computational ??uid 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 ??uid 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 (2002) we have studied an OS kernel for MIPS processor model. This project is support by 2002 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 MINIMUM SET-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) co-allocating resources, and (d) supporting quality of service.
In Operating Systems Lab., we have develop a project which studies a novel, highly decentralized, GridOS architecture that borrows features from Internet routing architectures. Our GridOS 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 GridOS runs on each node that participates in the Grid. Therefore, it is essential that the GridOS is lightweight so that the overhead is minimal and at the same time powerful enough to support different services. Our GridOS provides a service mobility protocol to migrate/replicate services depending on the demand.
|
| [minyi-01:2002] | Minyi Guo, Weng-Long Chang, and Yi Pan. Optimization Techniques for Parallelizing Irregular Scien??tic Codes. IPSJ Transactions on High Performance Computing Systems, 44:29-40, 2003.
In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. For an irregular loop with nonlinear array subscripts, the loop is transformed to a normalized single loop, then we partition the loop iterations to processors on which the minimalcommunication cost is ensuredwhen executing those iterations. We also give some interprocedural optimization techniques for communication preprocessing when the irregular code has the procedure call. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules. |
| [minyi-02:2002] | Yi Pan, Joseph J.S. Shang, and Minyi Guo. A Scalable HPF Implementation of Finite Volume CEM Application on a Cray T3E Parallel System. Concurrency and Computation: Practice an Experience, 15(6):607-621, 2003.
In this paper, we discuss an eAEcient and scalable parallelization of the sequential Fortran time-dependent Maxwell 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 Cray T3E 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-03:2002] | Meng Yu, Guihai chen, Xuelin Yang, Li Xie, and MinyiGuo. Japs-II: Parallelizing Compilers for Java. Journal of Software, 13(4):739-747, 2002.
Object-oriented features of object-oriented languages, such as polymorphism, small function and inheritance, exacerbate the direct application of traditional parallelizing techniques. To address these challenges, we design and implement a Java parallelizing compiler named JAPS-II. JAPS-II exploits and implements intra and interobject parallelism of sequential Java programs automatically. No explicit parallel directives are needed. JAPS-II's target codes are Java source programs that implement parallelism with Java threads. JAPS-II generates Java RMI interfaces when target system is NOW based distributed memory system. This paper introduces the architecture of JAPS-II and key techniques of implementing JAPS-II. These techniques include data flow analysis, parallelizing transformation, invocation localizing optimization, class restructuring and code generation. The e??ectiveness of these techniques is demonstrated through ultra linear speedup achieved in our experiments. |
| [minyi-04:2002] | Meng Yu, Wanyu Zang, Li Xie, Zhongxiu Sun, and Minyi Guo. Method Invocation Localizing Optimization in parallelizing Object-oriented Language. Chinese Journal of Computers, 25(4):409-416, 2002.
Techniques of parallelizing object-oriented language have borne many fruits in recent years. We introduce these new techniques in the aspects of parallel execution model, parallel facilities, optimization and runtime support mainly based on Ment at, CC++, pC++, HPC++, ICC++. We also describe our analysisand evaluation and introduce the problems that should be resolved in the future. |
| Referred Proceeding Papers |
| [minyi-05:2002] | Zhen Liu and Minyi Guo. Integrating Data Mining and On-Line Analytical Processing on Decision Support System. In Proceeding of SCI2002, Orlando, Florida, July 2002. |
| [minyi-06:2002] | Weng-Long Chang and Minyi Guo. Resolving the 3-Dimensional Matching Problem and the Set Packing Problem in Adleman-Lipton's Model. In Hisao KamedaEditor Jie Li, Kazuhiko Kato, editor, Proceedings of the 2002 IASTED International Conference of Network, Parallel and Distributed Processing, and Applications, pages 455-460, Tsukuba, October 2002. IASTESD, ACTA Press. |
| [minyi-07:2002] | Weng-Long Chang and Minyi Guo. Solving the Clique Problem and Vertex Cover Problem in Adleman-Lipton's Model. In Hisao Kameda Editor Jie Li, Kazuhiko Kato, editor, Proceedings of the 2002 IASTED International Conference of Network, Parallel and Distributed Processing, and Applications, pages 455{460, Tsukuba, October 2002. IASTESD, ACTA Press. |
| [minyi-08:2002] | Weng-Long Chang and Minyi Guo. Solving NP-Complete Problem in the Adleman-Lipton Model. In Editor Qun Jin, DamingWei, editor, Proceeding of The Third International Conference on Computer and Information Technology, pages 157-162, Aizu-Wakamatsu, Sept. 2002. Univ. of Aizu.
In this paper, we discuss how the DNAoperations presented by Adleman and Lipton can be used for developing DNA algorithms to solve the independent-setproblem |
| [minyi-09:2002] | Zhen Liu and Minyi Guo. A New Method of Consistency Management and Pair-wise Comparison Matrix. In Editor Qun Jin, Daming Wei, editor, Proceeding of The Third International Conference on Computer and Information Technology, pages 178{183, Aizu-Wakamatsu, Sept. 2002. Univ. of Aizu. |
| [minyi-10:2002] | Weng-Long Chang and Minyi Guo. Solving the Dominating-Set Problem in Adleman-Lipton's Model,. In Editor Susumu Horiguchi, editor, Proceedings of The Third International Conference on Parallel and Distributed Computi ng, Applications, andTechnologies, pages167-172, Kanazawa, Japan, Sept. 2002. JAIST.
In this paper, it is shown how the DNA (DeoxyriboNucleic Acid) operations proposed by Adleman and Lipton can be employed towards developing an efficient DNA algorithms to solve the dominating-set problem |
| [minyi-11:2002] | Weng-Long Chang Minyi Guo and Yi Pan. Optimization Techniques for Parallel Codes of Irregular Scienti??c Computations. In Procedings of The 4th Workshop on High Performance Scienti??c and Engineering Comput ing with Applications, pages 405-413, Vancouber, Canada, August 2002. IEEE Computer Society, IEEE Computer Society Press.
In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. For an irregular loop with nonlinear array subscripts, the loop is transformed to a normalized single loop, then we partition the loop iterations to processors on which the minimal communication cost is ensured when executing those iterations. We also give some interprocedural optimization techniques for communication preprocessing when the irregular code has the procedure call. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules. |
| [minyi-12:2002] | Minyi Guo, Zhen Liu, Chengfei Liu, and Li Li. Reducing Communication Cost for Parallelizing Irregular Scientific Codes. In Procedings of The 6th International Conference on Applied Parallel Computing, LNCS 2367, pages 203{216, Espoo, Finland, June 2002. University of Helsinki, Springer-Verlag.
In irregular application codes, use of indirection in accessing left hand side array makes it difficult to partition the loop iterations, and because of use of indirection in accessing right hand side elements, we may reduce total communication by using heuristics other than owner computes rule. 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. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules. |
| [minyi-13:2002] | Zhen Liu and Minyi Guo. A Proposal of High Performance Data Mining System. In Procedings of The 6th International Conference on Applied Parallel Computing, LNCS 2367, pages 106-115, Espoo, Finland, June 2002. University of Helsinki, Springer-Verlag. |
| [minyi-14:2002] | Weng-Long Chang Minyi Guo and Li Li. EAEcient Loop Partitioning for Irregular Applications. In Procedings of The 5th International conference on Algorithms and Architecture for Parallel Processing, pages 60-70, Beijing, China, October 2002. Chinese Academy of Science, IEEE Computer Society. |
| [minyi-15:2002] | Minyi Guo. Automatic Parallelization and Optimizations for Irregular Applications, Ministry of Education Grant-in-Aid: BasicResearch (C), Contract No. 14580386, 2002-2003. |
| [minyi-16:2002] | Minyi Guo and Ikuo Nakata. Optimization for Irregular Applications in Parallelizing Compilers, Okawa Foundation for Information and Telecommunication, 2001-2002. |
| [minyi-17:2002] | Minyi Guo, 2002. member, IEICE |
| [minyi-18:2002] | Minyi Guo, 2002. member, IEEE, IEEE Computer Society |
| [minyi-19:2002] | Minyi Guo, 2002. member, ACM |
| [minyi-20:2002] | Minyi Guo, 2002. member, IPSJ |
| [minyi-21:2002] | Minyi Guo, Apr. 2002. Program Committee member, The 3rd Workshop on Parallel and Distributed Scientific and Engineering Computing with Applications (PDSECA-02), IEEE Computer Society |
| [minyi-22:2002] | Minyi Guo, October 2002. Program Committee member, The 5th International conference on Algorithms and Architecture for Parallel Processing (ICA3PP2002), IEEE Computer Society |
| [minyi-23:2002] | Minyi Guo, Sept. 2002. Program Committee member, The Third International Conference on Parallel and Distributed Computing, Applications, and Technologies (PDCAT2002), IEICE, IPSJ |
| [minyi-24:2002] | Minyi Guo, August 2002. Program Committee member, The 4th Workshop on High Performance Scientific and Engineering Computing with Applications ( HPSECA-02), IEEE Computer Society |
| [minyi-25:2002] | Minyi Guo, Sept. 2002. Program Committee member, The 1st Workshop on Hardware/Software Support for parallel and Distributed Scienti??c and Engineering Computing (PACT-SPDSEC02), ACM |
| [minyi-26:2002] | Minyi Guo, December 2002. Program Committee member, The International Workshop on Grid and Cooperative Computing (GCC 2002), Chinese Academy of Science |
| [minyi-27:2002] | Ken'ichiro Funakubo. Graduation Thesis: Graphical User Interface of Memory Management System Simulator, University of Aizu, 2002.
Thesis Advisor: Minyi Guo. |
| [minyi-28:2002] | Yoshihiro Saitoh. Graduation Thesis: Memory Management System Simulator with Virtual Addressing, University of Aizu, 2002.
Thesis Advisor: Minyi Guo. |
|
Annual Review 2002