PLEIADES: An Internet-based parallel/distributed system

SOFTWARE—PRACTICE AND EXPERIENCE Softw. Pract. Exper. 2002; 32:1035–1049 (DOI: 10.1002/spe.468)

PLEIADES: An Internet-based parallel/distributed system D. Koulopoulos, K. Papoutsis∗,† , G. Goulas and E. Housos Computer Systems Laboratory, Department of Electrical and Computer Engineering, University of Patras, GR-26500 Rio, Patras, Greece

SUMMARY The use of LAN-based clusters of computers for computational purposes has been in use for several years with significant success and acceptability. The introduction of the Internet infrastructure as the interconnection medium of the cluster allows for additional flexibility and transparency of such systems. PLEIADES is an Internet-based parallel/distributed system whose purpose is to allow users to use distant computational resources in order to form virtual clusters. In addition, PLEIADES can be used as a computational infrastructure service provider for applications in need of computational resources. PLEIADES uses a tiered architecture with particular emphasis on the existence of a middle tier, whose task is to assist in the communication between the interface and the resource management tiers. The existence of the middle tier allows for the creation of an open system that is able to easily integrate with new resource management platforms and tools. Since the use of a mature resource management system for parallel/distributed computing was a prerequisite of the PLEIADES architecture, the Condor resource management environment was used. The design and implementation characteristics of PLEIADES together with some experimental uses of the system are also presented. Copyright  2002 John Wiley & Sons, Ltd. KEY WORDS :

parallel/distributed computing; service provider; Condor; XML

INTRODUCTION The existence of a high-bandwidth interconnection network among most university and research centers has given new potential to applications like Internet-based parallel/distributed processing and remote application access and submission, that were traditionally perceived as LAN-based applications. In particular, the possibility to consider resources, which were, from a communication point of view, difficult to reach and utilize as part of the local computation environment, has given a new rationale for the creation of Internet-based computer clusters. These developments have also been

∗ Correspondence to: K. Papoutsis, Computer Systems Laboratory, Department of Electrical and Computer Engineering,

University of Patras, GR-26500 Rio, Patras, Greece. † E-mail: [email protected]

Contract/grant sponsor: Greek General Secretariat of Research and Technology, Program PENED 99

Copyright  2002 John Wiley & Sons, Ltd.

Received 20 July 2001 Revised 2 January 2002 Accepted 14 March 2002

1036

D. KOULOPOULOS ET AL.

fueled by the fact that most computers are presently ‘always on and connected to the Internet’ [1]. It is well established that the average utilization of computers has been significantly reduced as the world has shifted from mainframe computing to the workstation-computing era. For the efficient utilization of the available computing resources, the distributed computing paradigm through the formation of ‘grid computers’ [2] appears to be the winning strategy for producing effective and scalable solutions. Even though hardware is always getting faster, for several important classes of problems, such as simulation and scheduling, there is a need for larger machines and additional computing power in order to achieve better and faster solutions. Thus, the scalability offered by the distributed computing paradigm in conjunction with the utilization of idle machines around the globe makes this strategy extremely attractive. In order to apply this paradigm, distributed computing platforms capable of utilizing the idle workstations are needed. A system that would allow every owner of a particular machine to volunteer the use of his/her machine, perhaps in order to gain some credits towards some later usage of other machines, should be similar to the traditional network of workstations (NOW) and Beowulf experiments, with the exception that the machines are now distributed over the Internet [3,4]. In addition, there are new challenges that need to be addressed involving primarily network, fault tolerance and flexibility issues. Being in a dynamic and ever shifting environment, it is impossible to assume that every user should have actual computer rights and accounts for every available machine, which implies that a different organizational scheme should be introduced. In this paper, the computer and network infrastructure of a typical university environment as well as the user requirements for processing power are examined. Many departments have shifted away from the central university-wide mainframe support, and have developed departmental computer centers. Moreover, in most cases, strong computer servers have sprung up even on the laboratory level. The costs of maintaining and upgrading computer resources are very high and the efficient use of the machines while they are still in their prime is essential. At the same time as these developments in the computing resources have been taking place, powerful networks and standard Web interface products for all users have created a new computational environment. Moreover, the use of XML [5] as the de facto information exchange standard has allowed for the smoother exchange of information between machines. The use of the browser for the interaction and communication with a universitywide server, whose purpose is to manage the computational resources and make them available to the whole user community, is now possible without sacrificing system reliability and ease of use. The PLEIADES system proposed in this paper can be used as a computational infrastructure service provider whenever the solution of an application is desired, but the required processing power is not available. In particular, whenever user applications that are submitted to an application service provider (ASP) require a specific set of machines, the PLEIADES system described in this paper would provide a distributed environment for the selection, prioritization and assignment of resources to the user applications. In the current implementation, PLEIADES relies on the infrastructure of the Condor‡ system [6,7] developed at the University of Wisconsin–Madison. Condor provides resource management and cluster creation services which could then be used for the creation of a high throughput computing (HTC) environment by effectively harnessing the power of a cluster of

‡ The Condor Software Program (Condor) was developed by the Condor Team at the Computer Sciences Department of the

University of Wisconsin–Madison. All rights, title and interest in Condor are owned by the Condor Team. Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

PLEIADES: PARALLEL/DISTRIBUTED SYSTEM

1037

workstations. Condor provides distributed processing services [8] and supports the message passing libraries PVM [9] and MPI [10]. PLEIADES as an open system has been designed in a manner that allows the use of new resource management systems that introduce policies more desirable to the end users. The PLEIADES system has many similarities with projects in the areas of meta-computing and Internet-based parallel computing and all of the systems that allow access to remote resources through Web-based interfaces. The Meta-Neos project provides meta-computing services over the Web in order to solve large optimization problems using their software and hardware resources [11]. The Meta-Neos project is oriented towards optimization problems and does not allow users to run their own executables on the system. JAVADC [12] provides a Web-based framework for the execution and monitoring of distributed applications written in PVM [9], pPVM [13] and MPI [10]. WebFlow [14] also provides a general-purpose Web-based visual interactive programming environment for distributed computing. Its successor, the Gateway project [15], provides seamless and secure access to computational resources. The Gateway has a very generic component-based architecture that uses Java components as proxies for particular back-end services such as DBMS (Data Base Management System) and resource managers. WebSubmit [16] and UNICORE [17] aim at providing secure simplified and unified access to existing high-performance computing systems. The remainder of this paper presents the PLEIADES system requirements, a detailed description of the PLEIADES prototype and all of its subsystems, two use case situations and our conclusions.

PLEIADES SYSTEM REQUIREMENTS The existence of a large number of powerful, always-connected and under-utilized computers, together with the dramatic explosion in the use of the Internet, was the main motive for the PLEIADES system initiative. The goal of PLEIADES is to satisfy the computational needs of a typical university environment that has a high-bandwidth interconnection network and a large set of available and underutilized computers. In addition, PLEIADES is targeted for use by a group of universities and research centers interconnected with a high-bandwidth network. A necessary process that the PLEIADES system must include is the ability of computer owners to donate CPU cycles to other users. The PLEIADES system should recognize a user type whose role is to allow the addition of his/her machine in the PLEIADES pool of machines; they will be called donor-users for the remainder of this paper. The users that take advantage of the donated CPU cycles by executing their applications on the PLEIADES platform will be called acceptor-users or simply users. Another category of users required for various administrative and security tasks forms the administrator-users group of PLEIADES. An essential requirement of PLEIADES involves the ability of users to form clusters of computers which should operate in a NOW [3] manner and solve, in a parallel/distributed manner, any computationally and/or memory intensive problem. In addition, PLEIADES, by being an open and flexible system, should be able to function as a computational infrastructure service provider (CISP) for the computational support of application service providing situations. Application service providing is a new approach to offering software whose main characteristic is that it provides Internet-based use of various software applications for use by a set of users who will never need to actually install such software on their individual machines. The ASPs, besides their software applications, also do not own Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

1038

D. KOULOPOULOS ET AL.

Submit and manage availability

PLEIADES

Submit and manage jobs

I D C

ASP User (donor)

Administer System

Submit and manage jobs

User (acceptor) Administrator PLEIADA pool

CN 's connected on the Internet

Figure 1. The PLEIADES system.

enough computing power for their processing needs and thus the CISP category has been created in order to fulfill this need [18]. Based on these requirements, a specification view of PLEIADES is shown in Figure 1. PLEIADES underpinning services PLEIADES provides the services shown in Figure 2 in order to allow users to perform all the required functionalities described in the previous section and create the illusion of a virtual computer facility. These services were prioritized based on the computational needs of a typical university environment that was the driving force for this work. Finding the CPU cycles in the appropriate computers for the available user binaries is the most important service that is provided. If this is not possible, which can often happen in a non-homogeneous university environment, a compilation service is also provided in order to create binaries for machines that currently exist in the PLEIADES pool. The most critical service of PLEIADES allows the users to submit their jobs for execution in distant machines. The job submission service allows the user to select the application executables and I/O files, as well as the number and platform of the required processors. Following a job submission step, the resource and process monitoring services maintain the status of each resource and process of the system. The resource and process monitoring services allow users to observe the status and progress of their work and receive progress and system messages. There is also a facility to define the conditions for a donor to reclaim full or partial use of a donated machine, and the signals and parameters that PLEIADES utilizes in order to consider a particular Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

PLEIADES: PARALLEL/DISTRIBUTED SYSTEM

Job Submission

Process Monitoring

Resource Monitoring

File Management

PLEIADES System

User Logging & Security

Cross Compile

1039

Computational Node Management

Figure 2. PLEIADES services.

machine available for the execution of its computational load. In some manner, this is similar to the kickoff mechanism of a typical screen saving process that exists in most personal computers. In addition, the Computational Node management service supports the actual insertion of a workstation into a PLEIADES working pool, and provides a mechanism for its removal from the pool. Security and logging services are also established for the various parts of the system. Each user is allowed to access only certain resources and services in accordance with the needs and permissions of the particular user group. The main security issue of such a system involves the full protection of the donor systems from malicious processes. Given that in a typical university environment there is some tolerance on system availability issues, well-established security strategies should be enough for PLEIADES. The full security extent of such systems is an active research area for GRID-type computing platforms. For the efficient management and organization of the tasks of each user, file management services are also provided. For each user there exists a separate file space in which files can be transferred, edited and manipulated. This allows for easy access and control of application binaries, input and output files. Since applications are often developed on a particular workstation, executables for the different possible platforms that PLEIADES might possess are not easily creatable. In order to overcome this weakness, a new and innovative service that enables the user to compile, in advance, the source files in distant machines is also provided. In Figure 2, this service is called cross-compile. PLEIADES iNOW functionality requirements Recently, the trend has been to utilize more than just one workstation in order to achieve faster and possibly better solutions for computationally intense problems. The use of a group of workstations for the solution of a problem was initiated by the NOW project [3] and has since been further streamlined in the Beowulf [4] and many other similar projects [11,13,19,20]. The use of the Internet, rather than a single LAN, as the interconnection medium for the formation of computer clusters to be used in a parallel/distributed manner is more flexible and has a greater growth potential [11,16,20]. This kind of Internet interconnected cluster will be named iNOW for the remainder of this paper. Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

1040

D. KOULOPOULOS ET AL.

The use of the Internet as the interconnection medium requires that the parallel/distributed applications that would use iNOW must satisfy certain rules in order to attain significant benefits from such an architecture. If computers are interconnected by a high-bandwidth network that it is not overloaded when the virtual cluster is in use, the expected performance difference between the NOW and the iNOW cases should be minimal. Thus, applications that use a LAN-based NOW should perform satisfactorily in an iNOW environment if they have a significant amount of parallel computation load and are able to implement strategies for fault tolerance, dynamic cluster allocation and resizing. PLEIADES using the services of the previous section should allow for the creation of iNOW environments where the user would be able to define the number and platform of required processors and memory capacity. The required binaries and input files for the application at hand should be transferred in the PLEIADES file space in advance and any required cross-compiling processing should be supervised by the user. PLEIADES as a CISP The use of the ASP approach for the solution of various problems is recently becoming mainstream, due to the benefits and cost savings involved when various common and computationally intensive applications are maintained, shared, hosted and executed in a centralized environment [18]. In a university environment, which is the focus of our work, the existence of several university-wide ASPs in cooperation with PLEIADES will assist in avoiding the under-utilization of the computer resources and the better availability of many popular applications. PLEIADES should have a simple and well-defined interface to its services also designed for use by other computer users as well as human users. Through this interface, an ASP could submit its computational requests to PLEIADES, which then would act as a CISP for the various ASPs.

PLEIADES SYSTEM PROTOTYPE The PLEIADES system prototype architecture follows a multi-tier structure, as shown in Figure 3. The functionality of tier 1, PLEIADES Front-end Tier (PFT), involves, on the one hand, the interaction with human users that submit their applications for execution and, on the other hand, the interface with computer users such as ASPs. ASPs are treated as virtual users and the assumption is that a computerto-computer session without any human intervention must occur. The two subsystems of this tier handle the interfacing needs of PLEIADES. The Web GUI subsystem is used for the human interactions and the CISP Access Point is used for computer-to-computer interactions. The second tier, PLEIADES Middle Tier (PMT), provides an abstraction layer for the different resource managers that could be potentially used by the PLEIADES system. The third tier, PLEIADES Resource Management Tier (RMT), provides resource and job management services. The functional and implementation details of each tier are further analyzed and explained below. PFT The PFT includes the front-end manager (PFM) subsystem and two interface modules named Web GUI and CISP Access Point (CAP). The Web GUI implements a Web-based graphical user interface Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

PLEIADES: PARALLEL/DISTRIBUTED SYSTEM

1041

Administer System Administrator Submit and manage jobs

CISP Access Point (CAP)

Web GUI XML

Submit and manage jobs

XML

Application Service Provider (ASP)

Front-End Manager (PFM)

User (acceptor) Submit and manage availability

Front-END Tier (PFT)

XML Job Information and Data

User (donor)

Tier 1

XML

Middle-Tier (PMT) Tier 2

Job Submission and Management

Resource Management Tier (RMT)

Tier 3

PLEIADES pool Computational Nodes

Figure 3. The PLEIADES system components.

for the interaction of the system with the donor-, acceptor- and administrator-users. The CAP provides the ability for ASPs to effectively use PLEIADES for the execution of their jobs [18]. The PFM subsystem is able to support multiple access points like the Web GUI and CAP and provides them with a structured and transparent flow of control from the interface modules to any of the lower tiers of PLEIADES. The communication between the PFM subsystem and its access points is realized using XML documents. Web GUI The functionality of the Web GUI, besides the standard interface modules needed for the uploading and execution of user programs, also allows the interaction with the PLEIADES file space of each user. Using Web GUI, the user can perform the entire typical file and directory operations like edit, copy, rename, delete, etc. Also, the user can visualize the input and output files, perform job submission and Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

1042

D. KOULOPOULOS ET AL.

job run-time management and monitoring. For the job submission functionality the Web GUI allows the user to declare using a special form all the required details about the executables, platform needs, minimum number of processors required and the location of the input and output files. In addition, it gives the user the option to be notified by e-mail after the completion of the particular application. Another major task of the Web GUI subsystem involves the interface of the cross-compilation feature. This feature greatly facilitates the creation of executables for every computer platform supported by PLEIADES. The Web GUI also assists the donor users in downloading and installing the necessary software for the inclusion of their computers in the PLEIADES pool of machines. Also, Web GUI provides for the administrator user group a special set of administration tools such as user and job management and complete access to the entire file space. The Web GUI was implemented using PHP [21] running under the Apache Web server [22]. To ensure a basic level of security that appears to be acceptable for the PLEIADES prototype, since the deployment environment is a typical university campus, the widely accepted Secure Sockets Layer (SSL) Standard has been adopted and utilized [23]. Due to the research nature of this project, the PLEIADES prototype utilizes the openSSL software in order to issue certificates [24]. If PLEIADES should be used in a production environment, then a trusted third party Certificate Authority should be used to confirm the validity of the certificates. The user authentication and session management functionality of the Web GUI is provided with the use of the phpSecurePages component [25]. PhpSecurePages relies on MySQL DBMS [26] for the persistent storage of user sessions and login information, and provides the underpinning technology for distinguishing the various user roles in PLEIADES. For the user interface of the file management and organization service of PLEIADES, the WebExplorer component [27] was utilized. This component was significantly enhanced in order to meet all of the PLEIADES needs for this service. CAP The CISP functionality is an innovative feature of PLEIADES and it is provided to specific ASPs using the CAP subsystem. CAP provides an information exchange point in order for ASPs to utilize the PLEIADES system for their computational needs. The information exchanged, between PLEIADES and an ASP, is organized using the XML standard. Since the interaction between PLEIADES and an ASP is similar to a batch processing system, the CAP interface is stateless. This means that the ASP submits its computational task and disconnects. In order for the PLEIADES service request to be complete, information regarding the ASP-username, password and all job related data must also be included. CAP receives XML formatted documents that contain requests to services, and returns the appropriate response and results back in XML as well. For the transfer of XML documents, the POST method of the HTTP protocol [28] is used. CAP, besides forwarding to PFM the XML requests, also authenticates the various users. Responses from PFM are forwarded to the ASP client through the CAP subsystem. CAP requires the XML documents to be nested in a POST method HTTP request, exactly in the same message formatting as they would be submitted from an HTML form due to the general availability and wide usage of the HTTP protocol. CAP is implemented as a cgi-script, running under the Apache Web server. It is written in C++ and, in order to handle information formatted in XML, the IBM XML4C API is used [29] which consists of Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

PLEIADES: PARALLEL/DISTRIBUTED SYSTEM

1043

the Apache Project Xerces XML library [30] and the IBM ICU for international character sets support [31]. For the user authentication process, CAP also uses the database used by the Web GUI subsystem. PFM The PFM is a module designed to support multiple internal access points. In the current version of the PLEIADES system, CAP and Web GUI are the two internal clients of PFM. It is the responsibility of the CAP and Web GUI access points of PFM to ensure that the proper authentication procedures have been followed. This guarantees that if a request violates any security protocol items, then it will not have the possibility to harm the whole PLEIADES system. Therefore, we attempt to stop every suspicious service request during the earliest phase of its lifetime in the PLEIADES environment. The definition of the services and the validation of the requests are performed by the use of specific XML Document Type Definitions (DTDs). In most cases, the PFM module forwards the requests from the access points to the middle tier except for file management issues, which it resolves locally by itself. In a similar manner the PFM forwards the responses from the middle tier back to the access points. The files and directory structure that appear in the file management service, are actual files located in special directories of PLEIADES. There exists at least one directory for each user. The set of possible actions for these files and directories are requested by its access points in XML format. In Figure 4, the DTD describing all of the requests for the file management service is presented. Figure 5 contains an example of a specific request needed for the creation of a directory. PFM is written in C++ and, in order to handle information formatted in XML, the IBM XML4C API is used. PMT The PMT provides the services that are needed for the PFT to be able to actually perform its job and system management tasks. In other words, PMT allows the interface tiers and RMT to interact in a transparent and organized manner. The main reason for the existence of this tier is the definition and implementation of a well-defined API for the communication of the PFT with any particular implementation of the PLEIADES RMT. Besides the organizational benefits that this offers, it also enables the PFM subsystem to be independent from the Resource Management system of tier 3, because PMT hides all the interface and functional details of RMT. The most important services that the PMT provides to PFT are job submission, job monitoring, job control, and adding and deleting of hosts to the PLEIADES pool. For the PLEIADES prototype, live monitoring of running jobs has not been implemented. If this feature were indeed needed, CORBA [32] or a similar middleware solution for PMT would be required. In the PLEADES prototype, job management information is maintained in the PMT level. The information regarding job submission, job status and job history is maintained in the PLEIADES database. For each job, a record is kept and the current status of this job is always reflected in this record. A software agent periodically monitors the status of all jobs and updates the appropriate records. This information remains stored in the database after the completion of a job for information and statistical purposes. The services of PMT have been written in C++ and their communication with RMT has been fully customized for the Condor resource management system that is used in the present PLEIADES Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

1044

D. KOULOPOULOS ET AL.

Figure 4. DTD that describes the file management service requests.

Figure 5. A request to create a directory named test in the users file space. Note that the root directory for these operations is the user’s private directory.

Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

PLEIADES: PARALLEL/DISTRIBUTED SYSTEM

1045

prototype. For the XML parsing and processing needs the IBM XML4C API is used. The required DBMS services are provided by MySQL. RMT For the current implementation of PLEIADES, the RMT is implemented using the Condor resource management system [6,7]. One of the attractive characteristics of Condor is its ability to form efficient computer clusters from a given pool of available processors. The minimum requirement for a workstation to become a member of the PLEIADES pool is the installation of the client Condor software. This initial installation must be done by the system administrator for security, responsibility and liability related reasons. For PLEIADES when the Condor client process runs in a distant machine, it runs with the permission of the nobody account in order to ensure the integrity and security protection of the system. Condor does not require a network file system (NFS) for data transfer. For the execution of parallel/distributed jobs following the master/worker programming paradigm Condor uses the PVM message passing library. Condor provides services for submitting, monitoring and controlling serial or parallel jobs. In order for a job to specify its execution environment requirements, as they relate to the platform needed and number of processors desired, a special submit file is created at tier 2. This file contains all the parameters required by Condor to correctly manage and schedule the particular job. Based on these requirements Condor performs a sophisticated matching between the job requirements and the available resources and tries to perform the best assignment [33,34]. Condor requires one machine to be the master of the PLEIADES computer pool. This machine, called the Condor Master, contains the full Condor system and keeps track of all the running jobs, the available machines and their status. For each computational node (CN), Condor provides all the necessary functionality in order for the owner of the machine to define when the particular machine will be available for PLEIADES. In order to be able to run parallel/distributed jobs using the PVM messagepassing library, the Condor–PVM module must also be installed in each CN. For all parallel/distributed jobs, the master process must run on designated machines and if the executables for the particular machines are not available, the user can create them by utilizing the PLEIADES cross-compiling services.

PLEIADES PROTOTYPE USE EXPERIENCE In order for a user application to be executed on the PLEIADES system, certain standards and environment-specific guidelines should be observed. These guidelines apply primarily to the use of PLEIADES for the execution of parallel/distributed jobs. A serial application can be executed on the PLEIADES system without significant changes, except for the possible creation of new binaries using the PLEIADES cross-compile service, due to the present availability of different types of machines. The detailed requirements that should be satisfied by the parallel/distributed applications are called ‘PLEIADES Ready Requirements’ and are available on the PLEIADES Web site in order for new users to effectively utilize the specific programming details required. These requirements are actually a set of parallel programming guidelines necessary for the efficient execution of parallel/distributed applications submitted for execution to the PLEIADES system. Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

1046

D. KOULOPOULOS ET AL.

For the parallel/distributed processing situation, the programming model to be used in order to best utilize the PLEIADES system should follow the master/worker paradigm. Since the underlying support from the RMT of the PLEIADES prototype is based on the Condor system, the preferred messagepassing library in the development of the parallel/distributed applications is PVM. This message passing protocol selection is mainly due to the inherent ability of PVM to sustain an unexpected or planned loss of some of its workers that are part of the present working cluster. Of course, the addition of new processors to an already executing cluster of computers is also important for this type of application, and since PVM fully supports this feature, this makes the choice even more apparent. In practice, whenever the master process requests a new host, the RMT subsystem intercepts this request and attempts to locate an available machine to be used by the specific PVM virtual machine. The user-defined master process is responsible for the implementation of check-pointing schemes in order to achieve a certain degree of fault tolerance whenever some of its workers are lost due to a computer or network malfunction or an owner reclaiming his/her machine. In addition, the master should be periodically alerted on the availability of new hosts that could be added to the present group of workers. It should be clear that the worker code should be compiled under many different platforms in order to be able to use as many available machines as possible. It should be emphasized that, in contrast to the LAN-based NOW situation, the fault-tolerance capabilities of the master process are extremely important for PLEIADES-based applications, because the configuration of the virtual machine may change at any time due to new additions and/or eliminations of active processors from the PLEIADES pool of available resources. The importance of the master process and the extreme consequences when an actual loss of the master process occurs, create the need for a minimum set of dedicated machines that PLEIADES should attain and control in order to securely and efficiently host all of the master processes in these machines. iNOW use case PLEIADES was used for the solution of a typical crew-scheduling problem and the results obtained were very satisfactory. The authors of this paper, and the Computer Systems Laboratory in general, has extensive experience with the use of a LAN-based NOW environment for the solution of several difficult combinatorial problems, with particular emphasis on scheduling applications [35–39]. In order to fully test the environment and the computational infrastructure of the PLEIADES system, the pairing generation process of a typical airline-crew-scheduling application was used [35]. In this situation, the parallel step involves a parallel search procedure for the generation of new trips that satisfy a large set of rules and regulations. This is the most time-consuming step of the overall process taking up to 80% of the computation time required by the complete system. The computations involved in the generation process are such that each worker is required to communicate only with its master process in order to initially receive work to be executed by the worker and, later, return to its master legal trips for further processing and optimization. This application fully satisfies the basic requirements for efficient parallel/distributed applications, which can be visualized as processes with large independent computation components and small intervals of information exchange between the master and its workers. In more detail, the generation process involves a sequence of depth first search steps that could be executed in parallel on the starting entity level. The nodes of the search structure are basic sets of activities that, when connected in accordance with a set of rules and regulations, form legal trips Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

PLEIADES: PARALLEL/DISTRIBUTED SYSTEM

1047

for the airline crew. In the crew-scheduling application, each basic set of activities to be connected involves a set of flight segments, where a flight segment is defined as the indivisible work interval with a single departure and a single arrival associated with it. For the parallel/distributed version of the trip-generation part of this application, a close to optimal speedup has been obtained when a NOW environment is used [39]. In the PLEIADES prototype environment, which contains mostly dedicated computers connected using a university-wide high-bandwidth network, the observed performance was within 1% of the results of [39]. This is primarily due to the fact that the network delays for this particular application are, to a great extent, overlapped with the actual searching computations, because this application is both extremely parallel by nature and at the same time could be executed in an asynchronous manner. These observations make this one of the best-suited applications for the PLEIADES system. CISP use case In order to test the use of PLEIADES in the CISP situation that requires a computer to effectively control PLEIADES, a prototype ASP interface for a school timetabling application was created. This particular scheduling application was available and in common use at the Laboratory [40]. It is assumed that the ASP administrator has organized specific directories in the PLEIADES file space for use by various ASP applications in advance. The pre-installed applications can then be easily used by the regular users of the ASP. Note that the ASP regular users do not realize that PLEIADES exists and that its resources are actually used for the solution of their problems. For every user request for the solution of a timetabling problem, the ASP server creates the appropriate XML service request and sends it to the PLEADES CAP. Upon a completion notification, the ASP server requests the produced output which is then transferred, embedded in an XML formatted response. Then, the ASP server translates the output to a typical timetabling format. For the ASP server, a user interface was created as a Web application using Microsoft Active Server Pages technology. The Web server used was the Microsoft Internet Information Server. For the XML manipulation on the ASP, the Microsoft MSXML component was used, and as for the XML/HTTP requests to and from PLEIADES, the Microsoft [41] component was employed.

CONCLUSIONS A system, named PLEIADES, for the creation of virtual networks of workstations that exploits the existence of a high-bandwidth interconnection network among most universities and research centers of Greece, has been presented. PLEIADES utilizes the simplicity and uniformity that the Internet has created, in order to make the sharing of resources among different university and research groups feasible and productive. The performance of virtual clusters that was observed was comparable to a LAN-based NOW if the network was slightly loaded and the applications were amenable to parallel/distributed computation. In addition, the possibility of using the PLEIADES system for the execution of typical serial applications in need of significant computing resources, submitted either from an ASP or an actual human user, has been explored. The use of XML for the exchange of the appropriate information between the ASP and PLEIADES, and among the various PLEIADES, internal subsystems, gives Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

1048

D. KOULOPOULOS ET AL.

additional flexibility and module independence to the design. The PMT allows the system to easily incorporate new resource management systems as they become available, without requiring any change to the PFT. The special nature of the donated computer use on distant machines, which is mainly characterized by the fact that the computer owner can reclaim the use of the machine at any time, requires the use of a message-passing library that allows for such a removal to occur without a significant loss of work. Moreover, it should be the case that, if a single computer is reclaimed by its owner, the remaining cooperating processes running on the remaining computers of the specific virtual cluster will also not abruptly terminate. For the present resource manager used in PLEIADES, this fact points to the use of the PVM message-passing library for the creation of the parallel/distributed applications, although MPI-based applications give better performance results when special multiprocessor machines are also involved in the cluster. The additional use of PLEIADES for research and development purposes is planned. The new training and the special tools needed for a parallel/distributed platform to be effectively used is, in many cases, the basic obstacle for the extensive use of this type of system. However, the use of PLEIADES as a resource management system for the scientific community, even when traditional applications are involved, appears possible and extremely desirable.

REFERENCES 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

Parnas DL. Always on: Living in a networked world. IEEE Spectrum 2001; 38(1):41–50. Foster I, Kesselman C. The Grid: Blueprint for a New Computing Infrastructure. Morgan-Kaufman: San Mateo, CA, 1999. Anderson T, Culler D, Patterson DA. A case for NOW (Networks of Workstations). IEEE Micro 1995; 38(1):54–64. The Beowulf Project site. http://www.beowulf.org. XML 1.0 Standard. http://www.w3.org/TR/2000/REC-xml-20001006. Basney J, Livny M. Deploying a high throughput computing cluster. High Performance Cluster Computing, vol. 1, ch. 5, Buyya R (ed.). Prentice Hall PTR: Englewood Cliffs, NJ, 1999. Livny M, Basney J, Raman R, Tannenbaum T. Mechanisms for high throughput computing. SPEEDUP Journal 1997; 11(1). Pruyne J, Livny M. Providing resource management services to parallel applications. Proceedings of the Second Workshop on Environments and Tools for Parallel Scientific Computing, May 1994. http://www.cs.wisc.edu/condor/doc/condor pvm framework.ps.Z. Geist A, Beguelin A, Dongarra J, Jiang W, Manchek R, Sunderam V. PVM: Parallel Virtual Machine. MIT Press, 1994. Gropp W, Lust E, Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. MIT Press: Cambridge, MA, 1994. Goux JP, Kulkani S, Linderoth J, Yoder M. An enabling framework for master–worker applications on the computational grid. Submitted to HPDC 2000 Conference Proceedings. http://www.mcs.anl.gov/metaneos/papers/mw2.ps [2000]. Maly K, Vangala PK, Zubair M. JAVADC: A Web–Java based environment to run and monitor parallel distributed applications. Technical Report, Old Dominion University, 1997. Maly K, Zubair M, Kelkar SU. A parallel and distributed computing environment for scientific applications. PhD Thesis, 1996. Bhatia D, Burzevski M, Camuseva W, Furmanski W, Premchandran G. WebFlow—a visual programming paradigm for Web/Java based coarse grain distributed computing. Concurrency: Practice and Experience 1997; 9(6):555–577. Fox G, Haupt T, Akarsu E, Kalinichenko A, Kim KS, Sheethalnath P, Youn CH. The gateway system: Uniform Web based access to remote resources. Proceedings of the ACM 1999 Conference on Java Grande, June 1999. ACM Press: San Francisco, CA, 1999; 1–7. McCormack R, Koontz J, Devaney J. Seamless computing with Web Submit. Concurrency: Practice and Experience 1999; 11(15):949–963. Almond J, Snelling D. Secure and uniform access to distributed resources via the world wide web. White Paper, October 1998.

Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049

PLEIADES: PARALLEL/DISTRIBUTED SYSTEM

1049

18. ASP—Application Service Providing, the Ultimate Guide to Hiring rather than Buying Applications. Edited by SCN Education BV Vieweg: Braunschreig, 2000. 19. SETI Institute Online. http://www.seti.org. 20. Good M, Goux JP. iMW: A Web-based problem solving environment for grid computing applications. MetaNEOS Project Technical Report. http://www.mcs.anl.gov/metaneos/papers/imw.os. 21. PHP Web site. http://www.php.net. 22. Apache Web server. http://www.apache.org. 23. Secure Sockets Layer (SSL) Standard. http://home.netscape.com/security/techbriefs/ssl.html. 24. OPEN SSL site. http://www.openssl.org. 25. PhpSecurePages component site. http://www.phpsecurepages.f2s.com/. 26. MySQL Relational Database Management System. http://www.mysql.org. 27. WebEplorer component site. http://www.suneworld.com/programs/. 28. HTTP Protocol. http://www.w3.org/Protocols/rfc2616/rfc2616.html. 29. IBM. XML4C API. http://www.alphaworks.ibm.com/tech/xml4c. 30. Apache Xerces for C++, Apache XML Project. http://www.apache.org. 31. IBM. Internal Components for Unicode (ICU). http://www.oss.software.ibm/com/icu/. 32. CORBA at the Object Management Group site. http://www.omg.org. 33. Raman R, Livny M, Solomon M. Resource management through multilateral matchmaking. Proceedings Ninth IEEE Symposium on High Performance Distributed Computing (HPDC9), Pittsburgh, PA, August 2000. IEEE Computer Society Press, 2000; 290–291. 34. Raman R, Livny M, Solomon M. Matchmaking: Distributed Resource Management for High Throughput Computing. Proceedings Seventh IEEE International Symposium on High Performance Distributed Computing, Chicago, IL, 28–31 July, 1998. IEEE Computer Society Press, 1998. 35. Housos E, Elmroth T. Automatic subproblem optimization for airline crew scheduling. Interfaces 1996; 27(5):68–77. 36. Alefragis P, Sanders P, Takkula T, Wedelin D. Parallel integer optimization for crew scheduling. Annals of Operations Research 2000; 99(1–4):141–166. 37. Alefragis P, Goumopoulos C, Housos E, Sanders P, Takkula T, Wedelin D. Parallel crew scheduling in PAROS. Europar’ 98, Southampton, 1–4 September, 1998 (Lecture Notes in Computer Science, vol. 1470). Springer: Berlin, 1998; 1104– 1113. 38. Goumopoulos C, Alefragis P, Housos E. High performance airline crew-pairing optimization. Auto-PDS98, Vienna, Austria, 1–3 July, 1998. IASTED/ACTA Press, 1998. 39. Goumopoulos C, Alefragis P, Housos E. Parallel algorithms for airline crew planning on networks of workstations. International Conference on Parallel Processing (ICPP-98), Minneapolis, MN, 10–15 August, 1998 (IEEE Conference Series PR08650). IEEE Computer Society Press: Los Alamitos, CA, 1998; 70–78. 40. Birbas T, Daskalaki S, Housos E. Timetabling for Greek high schools. Journal of the Operational Research Society 1997; 48:1191–1200. 41. Microsoft Corporation Web site. http://www.microsoft.com.

Copyright  2002 John Wiley & Sons, Ltd.

Softw. Pract. Exper. 2002; 32:1035–1049