Parallel and Distributed Computing

1.   Introduction

      As main streams of computer science and engineering, Parallel/Distributed Computing and Software Systems have developed more than 30 years in CSE department. The principle research areas in this division includes: parallel and distributed computing, theoretical computer science, software engineering, and e-learning. The research topics cover a broad spectrum including parallelizing compilers, software optimization for embedded systems, pervasive/ubiquitous computing, concurrency theory, the type theory and the related issues in formal method, aspect-oriented programming, software testing, and practical e-learning system. From 2002 to 2008, the division was funded by National High-Tech Plan (863), National Natural Science Foundation of China (NSFC), Ministry of Education, etc. It has finished more than 60 research projects with RMB 19 million Yuan research funding. Now the division has 15 faculty members, in which there are 7 full professors, 4 associate professors and 4 assistant professors. The division has 22 Ph.D. students, and 43 master students. Two professors got NSFC Distinguish Young Scholar Award and one professor got He-Liang-He-Li Scientific Award.

       In these areas, the professors and students have published more than 70 international journal papers and 300 international conference papers in the past five years, including prestigious journals such as IEEE Transactions on Parallel and Distributed Systems, IEEE Transactions Multimedia, IEEE Transactions on Nanobioscience, Theoretical Computer Science, Journal of Symbolic LogicSIAM Journal on Computing, Journal of Parallel and Distributed Computing, and prestigious international conference such as InfoCom, ICS, IPDPS, LICSICALPFASEAOSD, PACT.

       In parallel/distributed computing area, Dr. Guo Minyi’s group proposed some efficient techniques for data distributed and redistribution on massively parallel computers, communication optimization techniques for irregular computation, and used these methods into the Fortran Compiler in CP-PACS parallel computer. The related papers on this topic have been cited more than 250 times by other research papers.

       The research team leaded by Dr. Fu Yuxi on basic theory of computer science is the first class in domestic universities. In parallel computing field, the team researched the semantics of various concurrent computing models, and applied the results to practical problems solving including software systems and security protocols. The results were published on SIAM Journal and

    Professor Shen Ruimin’s research on E-learning focuses on the intelligent and personalized models and methods. They set up a set of new computer-supported education models. Dr. Shen has constructed a real E-learning system and practiced in national distance learning system. The achievement was awarded the first class reward of Shanghai government Science & Technology. Dr. Eric Hamilton, director of education and human resource development of National Natural Science Foundation of America, commented this result as “one of the best E-Learning work in the world”

 In the next few years, the division will focus on researching on pervasive/ubiquitous computing, embedded computing and low power optimization for multi-core architectures, concurrency theory and formal validation, digital distance learning technology, using current research results to apply on Traffic Control, Water Conservancy Monitoring, Colliery Security, Shanghai World Expo, Power System Monitoring and Long-Distance Education. We hope to publish average 20 papers per year on prestigious journals and conference like IEEE Transactions on Computer, IEEE Transactions on Parallel and Distributed Systems, IEEE Transactions on Networking, ACM Transactions on Architecture and Code Generation, ACM Transactions on Embedded Computing Systems and INFOCOM, CCSIEEE P & S, FOCSLICSICALPFASEAOSD, Crypto. We plan to graduate five Ph.D students and let them recruit the position in the same level universities in the world.

 

2.    Faculty Members

    In this research direction there are 7 full professors, 4 associate professors and 4 assistant professors. The resumes of some professors are given below.

Guo Minyi was born in 1962. He is a Special Appointment professor of Shanghai Jiao Tong University. He received the Ph.D. degree in computer science from University of Tsukuba, Japan. Before 2000, Dr. Guo had been a research scientist of NEC Corp., Japan. He was a full professor at the Department of Computer Software, the University of Aizu, Japan. He was also a visiting professor of Georgia State University, USA, Hong Kong Polytechnic University, University of Hong Kong, National Sun Yet-sen University in Taiwan, University of Waterloo, Canada and University of New South Wales, Australia. Now Dr. Guo is Distinguish Chair Professor of Shanghai Jiao Tong University, China. Dr. Guo has published more than 170 research papers in international journals and conferences. Dr. Guo has served as general chair, program committee or organizing committee chair for many international conferences. He is the founder of International Conference on Parallel and Distributed Processing and Applications (ISPA), and International Conference on Embedded and Ubiquitous Computing (EUC). He is the editor-in-chief of the Journal of Embedded Systems, as well as in editorial board of Journal of Pervasive Computing and Communications, International Journal of High Performance Computing and Networking, Journal of Embedded Computing, Journal of Parallel and Distributed Scientific and Engineering Computing, and International Journal of Computer and Applications.

He has been supported by the National Science Fund for Distinguished Young Scholars, the National Natural Science Foundation of China and 863 program since 2005.

  Fu Yuxi was born in 1962. He is a full professor and serving as the departmental chairman, the dean of the School of Software, and the director of BASICS, the Laboratory for the Basic Studies in Computing Science, supported by the Shanghai Education Commission. Also, he is the executive member of Asian Association for Foundation of Software (AAFS). He received Ph.D degree from The University of Manchester in 1992, supervised by famous computer scientist David Rydeheard. His research interest is in theoretical computer science, focusing mainly on the concurrency theory, the type theory and the related issues in formal method. Dr. Fu has published more than 30 papers in international journals. His research was supported by the National Science Fund for Distinguished Young Scholars, the National Natural Science Foundation of China and 863 program.

 Shen Reiming was born in 1967. He is the full professor of Department of Computer Science and Engineering, Shanghai Jiao Tong University, the member of long-distance education expert committee of education ministry, the director of Shanghai long-distance education research center, and the dean of network education school of Shanghai Jiao Tong University. His research interests focus on e-learning. His research team set up an intact and practical e-learning system, which was awarded the first class reward of Shanghai government Science & Technology. Dr. Eric Hamilton, director of education and human resource development of National Natural Science Foundation of America, commented this result as “one of the best E-Learning work in the world”.

    Zhao Jianjun is a full professor in the Department of Computer Science and Engineering and the School of Software at the Shanghai Jiao Tong University. He received a BS degree in computer science from Tsinghua University in 1987 and a PhD degree in computer science from Kyushu University in 1997. His research interests include Aspect-Oriented Software Engineering and Program Analysis for Software Engineering and Compiler Optimization. He is also a member of the Center for Software Engineering.

   Wang Yinglin is a full professor in the Department of Computer Science at the Shanghai Jiao Tong University. He received a Ph.D degree in pattern recognition and intelligent control from Nanjing University of Science and Technology. In 2001 and 2005, he visited the University of Hong Kong and Stanford University for cooperative research. His research interests include adaptive enterprise information systems, and information integration, ontology engineering, cooperative knowledge management, semantic Web, e-business and workflow management, machine learning and data mining.

 

3.   Representative Research Achievements

 

Achievement 1: automatic and parallel program compilation and programming langue 

  In this area, we creatively proposed a set of data distribution and redistribution algorithms, and redistributed data scheduling. Traditional policies for data distribution are based on the Block-Cyclic, which is regular and easy to implement. But it is not applicable to irregular computing. We proposed a linear data distribution algorithm for irregular computing, which decomposes data in any linear expression. As a result, Block-Cyclic is only a subset of our approach. Furthermore, we designed a series of algorithms for data address conversion. In some parallel programs for science computing, data needs to be redistributed to multiple processors during different computing phases. It is the real-time overhead in the run-time so that the performance of algorithms directly affects the efficiency of program execution. We made a great contribution by proposing a 4-tuple description method for global data, based on which we investigated the formula of address mapping between before and after the data reallocation. The time spent on address computing reduces 20% by using this formula. On the other hand, we creatively applied the new conception of communication length alignment to data reallocation, which enormously improves the communication time. Now, this approach is widely used to solve similar problems.

    Our results were published on Journal of Parallel and Distributed, Journal of Supercomputing, Parallel Computing, IEICE Transactions on Information and Systems. The papers were cited by researchers of USA, Taiwan, Korea and so on. Some algorithms were integrated in MPI parallel library, MPI_Alltoallv. The cited times totally add up to more than 250. The papers published in Parallel Computing and The Journal of Supercomputing all were cited 84 times. Now, almost all papers submitted to IEEE Transactions on Computer, IEEE Transactions on Parallel and Distributed Systems, which involve in data distribution and reallocation, are reviewed by Prof Guo Minyi.

 

Representative papers published in recent 5 years supporting achievement 1:

1.   Minyi Guo, I. Nakata, and Y. Yamashita: Contention-Free Communication Scheduling for Array Redistribution, Parallel Computing (Elsevier Science), Vol. 26, No.10, pp. 1325-1343 (2000).

2.   Jingling Xue, Minyi Guo, and Daming Wei " Improving the parallelism of iterative methods by aggressive loop fusion ", The Journal of Supercomputing, Vol. 43, No. 2, 2008. pp. 147--164

3.   Hui Wang, Minyi Guo, and Daming Wei, " Message Scheduling for Irregulart Data Redistribution in Parallelizing Compilers ", IEICE Transactions on Information and Sysmtes Vol. E89-D, No. 2, pp. 418--424, 2006

 

Achievement 2: basic theory research on process computing, automata theory, model validation, algorithm and complexity analysis 

 

   We have systematically researched on theoretical computer science. Our research team on basic theory of computer science is the first class in domestic universities. This direction mainly researches on concurrency computing, algorithm and complexity, process calculus, semantics and model, automata theory, aspect-oriented software engineering, software testing and validation. In parallel computing field, we researched the semantics of various concurrent computing models, and applied the results to practical problems solving including software systems and security protocols.

   Currently, we have published a series of results in top international conference and journals such as Theoretical Computer ScienceInformation and ComputationJournal of Symbolic Logic, SIAM Journal on Computing, LICS, ICALP, FASE, AOSD. Many open issues were solved and a powerful research team is trained and set up. In algorithm complexity field, we researched the optimal algorithms and low bound for different computing. Moreover, we have created a new research direction, i.e., parameter complexity and relevant logic problems, made great results and achieved a first level all around the world. On the other hand, in the direction of parallel model researches, we are at the leading level. In past years, we published papers in top international conference LICS and journals TCS, JSL, APAL.

 

Representative papers published in recent 5 years supporting achievement 2:

1.    Yuxi Fu, Zhengrong Yang. Tau Laws for Pi Calculus. Theoretical Computer Science, 308, 55-130, 2003.

2.    Yuxi Fu, Fair ambients. Acta Inf. 43(8): 535-594 (2007)

3.    Xian Xu, Xiaoju Dong, Yuxi Fu, A Model in kappa for DNA Addition. Electr. Notes Theor. Comput. Sci. 171(2): 209-222 (2007)

 

Achievement 3: smart shadow based pervasive computing theory and technology

 

   Pervasive computing has two key features: (1) it provides information for users anytime anywhere; and (2) users can share computing and communication in the transparent way through deploying multiple sensors, embedded devices, mobile devices and others, reducing user interference as much as possible. Pervasive computing is an intelligent distributed computing paradigm, providing personalized services and the transparency of service process. Based on the features and requirements of pervasive computing, we research pervasive computing oriented smart shadow technology, and set up an uniform modeling systems for description and representation of objects’ properties and activities.

   We investigated the acquirement and management technologies of context knowledge, formally described the context information, mined and reasoned context knowledge and entity behavior. We also researched the discovery and integration technologies of pervasive resources, resource mapping and arbitration mechanisms, context based resource scheduling and reservation methods. By deep research on object description and acquirement, we have established object ontology, structure and reasoning rules, modeled and recognized user’s behavior, and achieved subject-driven human-machine interactions. At the same time, we investigated the communication and interaction, service discovery and composition mechanisms for pervasive middleware, implemented context based self-tailoring and adjusting technologies. Currently, we are developing and deploying intelligent pervasive campus, supported by the key project from NSFC, which aims at providing self-adaptive pervasive services for teachers and students.

 

Representative papers published in recent 5 years supporting achievement 3:

1.   Kaikai Chi, Xiaohong Jiang, Susumu Horiguchi, and Minyi Guo. Topology Design of Network-Coding-Based Multicast Networks. IEEE Transactions on Parallel and Distributed Systems, VOL. 19, NO. 5, MAY 2008, pp.627-640.

2.   Kaikai Chi, Xiaohong Jiang, Susumu Horiguchi, and Minyi Guo, " Topology Design of Network Coding-Based Multicast Networks ", IEEE Transactions on Parallel and Distributed Systems, Vol. 19, No. 5, 2008. pp. 627--640

3.   M.Mostafa A. Azim, Xiaohong Jiang, Pin-Han Ho, Susumu Horiguchi, and Minyi Guo, " Restoration Probability Modelling for Active Restoration-Based Optical Networks with Correlation Among Backup Routes ", IEEE Transactions on Parallel and Distributed Systems, Vol. 18, No. 11, 2007. pp. 1592--1606.

 

Achievement 4: DNA computing and bioinformatics

    Aldeman in the University of Southern California solved the Hamilton problem in polynomial time using DNA biology experiments in 1995. His paper was published in Science. Prof Guo Minyi proposed creatively a new approach, using a few biology experiment operations, i.e., extract, merge, anneal, connection. This approach solves successfully a few NP-complete problems, for example, Set-SplittingSubset-sumSet cover and Exact cover by 3-sets. Based on this, we implemented a set of simulation software for biology computing, and run some biology computing programs in our simulators. Our research team has published 12 papers on related research in IEEE Transactions on Nanobioscience, BioSystems, Parallel Computing, IEICE Transactions. Downloaded ratio of our papers is at the first 25 in Natural Computing, which includes many related journals. It is the first paper published in IEEE Transactions on Nanobioscience in mainland and attracted very much attention. Lauren Aaronson, a reporter of IEEE Transactions Spectrum arranged a special telephone interview to Prof Minyi Guo and published related news and comments.

 

Representative papers published in recent 5 years supporting achievement 4:

1.   Weng-Long Chang, Minyi Guo and Michael Ho, “Fast Parallel Molecular Algorithms for DNA-based Computation: Factoring Integers”, IEEE Transactions on Nanobioscience. Vol. 4, No. 2, pp. 149-163, 2005.

2.   Weng-Long Chang, Ting-Ting Ren, Jun Luo, Mang Feng, and Minyi Guo, " Quantum Algorithms for Biomolecular Solutions of the Satisfiability Problem on a Quantum Machine ", IEEE Transactions on Nanobioscience, Vol. 7, No. 3, September, 2008.

3.   Minyi Guo, Weng-Long Chang, Machael Ho, Jian Lu, and Jiannong Cao, "Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing ", BioSystems (Elsevier), Vol. 80, No. 1, pp. 71--82, 2005.

 

Achievement 5: Irregular scientific computing 

    Irregular computing deals with the ruleless data structure, which cannot be described using simple data structure such as matrix, graphics, and tree. Irregular computing can be applied to many applications, such as fluid mechanics, molecular dynamics N entity problem. We proposed a series of novel mechanisms to improve the parallelism and resource usage. First of all, we proposed minimal communication based loop iteration algorithm, which allocate processors using our Least Communication Rule rather than Owner-Compute Rule in each loop. It minimizes the communication traffic in each iteration. Experiment results show it can reduce parallel execution time at the same time it does not add extra overhead for iteration allocation in each execution. Next, we proposed optimization algorithms for irregular computing. So far, traditional parallel compilation methods only use parallel computing within a process, and do not develop the parallelism among processes. We successfully researched the parallelism among the processes, which improves the performance of parallel computing to some extent. Finally, we proposed a communication alignment based optimal method for data reallocation in irregular computing, and figured out corresponding scheduling algorithms, respectively. Related paper was published in the influential journal- Journal of Parallel and Distributed Computing.

   Our results have been published in many top international journals, for example, IEEE Transactions on Parallel and Distributed Systems, Journal of Parallel and Distributed Computing, Journal of Supercomputing, IEICE Transactions on Information and Systems. The totally cited times are more than 90.  Our work has wide impact all around the work. Dr. Guo Minyi was invited to make a keynote speech in IPDPS-PDSECA Workshop, which was held in Santa Fe, USA in April 2004.

 

Representative papers published in recent 5 years supporting achievement 5:

1.   Minyi Guo and Yi Pan, “Improving communication scheduling for array redistribution”, Journal of Parallel and Distributed Computing (Elsevier), Vol. 65, No. 5, pp. 553—563, 2005

2.   Hui Wang, Minyi Guo, and Daming Wei, "Divide-and-conquer Algorithm for Irregular Redistributions in Parallelizing Compilers”, The Journal of Supercomputing (Kluwer Academic Publishers, Boston, USA). Vol. 29, No. 2, pp.157--170, 2004.

3.   Hui Wang, Minyi Guo, and Daming Wei, " Message Scheduling for Irregulart Data Redistribution in Parallelizing Compilers ", IEICE Transactions on Information and Sysmtes Vol. E89-D, No. 2, pp. 418--424, 2006.

 

Achievement 6: E-learning technology

   Our research on E-learning focuses on the intelligent and personalized models and methods, and set up a set of new computer-supported education models. The goal is to provide real-time and controllable education services for users with heterogeneous networks and terminals, and guide different users according to their personality and individual requirements. E-learning makes full use of the abilities of asynchronous and distributed information handling of Internet to meet the education requirements from our society. With the rapid development of Internet and wireless networks (GPRS,CDMA, 3G), e-learning will face many new challenges inWeb-based LearningBlended-LearningMobile-Learning. We are performing top research in new e-learning models and network services, and have published a series of results in top international conferences and journals, for example, Informatic, Information Sciences, Expert System With Applications, Electronics Letters, WWW, in personalized learning in the on-line fashion, intelligent Q&A system, digital watermark.

    We have developed many international cooperation with British Telecom (BT), German Research Center for Artificial Intelligence (DFKI), San Diego State University (SDSU) and our results are accepted by international experts. The chapter 4 of Web-Based Learning: Theory, Research and Practice introduces our models and applications. Eric. Hamilton, the director of US National Science Foundation (NSF) comments on our work as “one of the best e-learning work in the world”.

 

Representative papers published in recent 5 years supporting achievement 6:

1.     Ruimin Shen, Peng Han, Fan Yang, Qiang Yang, Joshua Zhexue Huang. Data Mining and Case-Based Reasoning for Distance Learning. Journal of Distance Education Technologies, 1(3), 46-58, July-Sept 2003, pp46-58.

2.     Liping Shen, Victor Callaghan, Ruimin Shen: Affective e-Learning in residential and pervasive computing environments. Information Systems Frontiers, 10(4): 461-472 (2008)

3.     Heng Luo, Changyong Niu, Ruimin Shen, Carsten Ullrich: A collaborative filtering framework based on both local user similarity and global user similarity. Machine Learning, 72(3): 231-245 (2008)

[ 2011-09-07 ]