This paper presents the main ideas of the high-performance component-based Grid programming environment of the Grid.it project. High-performance components are characterized by a programming model that integrates the concepts of structured parallelism, component interaction, compositionality, and adaptivity. We show that ASSIST, the prototype of parallel programming environment currently under development at our group, is a suitable basis to capture all the desired features of the component model in a flexible and efficient manner. For the sake of interoperability, ASSIST modules or programs are automatically encapsulated in standard frameworks; currently, we are experimenting Web Services and the CORBA Component Model. Grid applications, built as compositions of ASSIST components and possibly other existing (legacy) components, are supported by an innovative Grid Abstract Machine, that includes essential abstractions of standard middleware services and a hierarchical Application Manager (AM). AM supports static allocation and dynamic reallocation of adaptive applications according to a performance contract, a reconfiguration strategy, and a performance model. Components, Structured Parallel Programming, Programming Models, Grid, Adaptive Applications, High Performance Computing, Reconfiguration. In the context of Grid platforms at various levels of integration [1], a Gridaware application must be able to deal with heterogeneity and dynamicity in * This work has been supported by the Italian MIUR FIRB Grid.it project (RBNE01KNFP) on Highperformance Grid Platforms and Tools, and by the MIUR CNR Strategic Project L 499/97-2000 on Highperformance Distributed Enabling Platforms. 2 the most effective way (adaptive applications), in order to guarantee the specified level of performance in spite of the variety of run-time events causing modifications in resource availability (load unbalancing, node/network faults, administration issues, emergencies, and so on). With respect to traditional platforms, when the Grid is taken into account it is much more important to rely on application development environments and tools that both guarantee high-level programmability, application compositionality, software interoperability and reuse, and, they are able to achieve high-performance and the ability to adapt to the evolution of underlying technologies (networks, nodes, clusters, operating systems, middleware) [2] [3] [4] [5] [6] [7] [8] . Achieving this high-level view of Grid application development is the basic goal of our research, in the Grid.it national project [9] and in associated initiatives at the national and European level. In order to be able to design, develop and deploy such kind of high-performance Grid-aware applications efficiently, we are interested in innovative programming environments that i) support the programmers in all the activities related to parallelism exploitation, by providing some kind of structured primitives for parallelism exploitation; ii) allow to achieve full interoperability with existing software, both parallel and sequential, either available in source or in object form; iii) support and enforce reuse of already developed code in other applications. In particular, we want to exploit the experience of our group in the design and implementation of structured parallel programming environments [10] [11] [12] to target Grids composed of clusters or networks of heterogeneous workstations Table 1 . Layered software architecture for Grid-aware applications Complex, multidisciplinary applications. Programmer only expresses the kind of parallelism, without being concerned with any detail involved in its exploitation or related to the fact that the target architecture is a Grid. The user supplies, for each parallel component, a performance contract to be satisfied. Exploitation of structured parallelism, basic mechanisms supporting compositionality, interoperability and reuse of existing software, support for the dynamic control of performance contracts and adaptivity. Functionalities and mechanism supporting the programming environment, including dynamic application management and all the needed features from the resource, collective and connectivity levels of Grid middleware Components for . We think that a component-based programming environment is a suitable starting point to achieve the goals just stated. In this work, we discuss the essential features of a programming environment that is based both on the component model and on structured parallelism. The programming environment is a layer of a larger picture, such as the one in Table 1 . We will first discuss the features of a component-based parallel programming model. Then, we'll take into account how these features are currently or will be soon supported in ASSIST. ASSIST is a structured parallel programming environment that was originally designed to address cluster and networks of TCP/IP workstations only, in the framework of the Italian national project ASI-PQE2000 [18] . We show that ASSIST is a suitable basis to capture all the desired features in a flexible and efficient manner, and, in particular, we discuss how the original ASSIST environment is currently being transformed into a component-based, Grid-aware parallel programming environment. This evolution of the ASSIST environment is being performed in the framework of the Grid.it Italian national project. Grid.it is a 3 year project involving major research institutions in Italy aiming at providing innovative programming methodologies and tools for Grids. The project has a specific work-package, leaded by our group, aimed at designing and implementing a prototype highperformance parallel programming environment for Grids. Component-based ASSIST is the expected, assessed outcome of this work-package. Several studies recognized that component technology could be leveraged to ease the development of Grid applications. We assume as reference component standards the CORBA Component Model (CCM), because of its clean and rich component model [19] [20] , and the Web/Grid Services [21], because they are emerging as the standard infrastructure to integrate heterogeneous systems [21] . The Common Component Architecture (CCA) is a prominent standardization effort, aiming at the definition of a high-performance oriented component architecture [22] . We depart from CCA-based approaches like CCaffeine [23] as we explicitly deal with component composition issues (see Sect. 1.2 and Sect. 1.3.2). Our approach differs from that of GridCCM [24], as the latter focuses on communication optimization, while our work targets application adaptivity and Grid-awareness in general. We are closer to the GrADs project [25] with respect to the concept of adaptivity and in some architectural aspects, but we differentiate in the programming model. Our model, being based on structured parallel programming, has the ability i) to synthesize from the parallel structure of applications the performance models used to adapt their computation, and ii) to control the applica-4 tion configuration at run-time, using a parametric implementation of the parallel programming constructs. A closely related project to our one is ProActive [26] , which extends the Fractal component framework for Java [27] to support parallel, reconfigurable component architectures on the Grid. We share with the Proactive project the departure from flat component models to move toward explicit component composition, the emphasis on run-time adaptivity of component structures, and the exploitation of these hierarchical structures to manage application reconfiguration. We differentiate from that research as we are not limited to Java, we have instead a well defined, language-based separation between sequential program behaviour and parallel coordination, at the intra-and inter-component levels. Our primary goal in improving component interaction is also different, as we want to exploit a broader set of interaction mechanisms than RMI. On the contrary, Proactive primarily exploits parallel and collective RMI abstractions (and their optimizations e.g. by means of futures) to extend the sequential component framework to a parallel, distributed one. High-performance components for Grid-aware applications: computational model The basic features needed to implement a component-based, high performance programming environment targeting the Grid include most of those already implemented in currently available component models, such as JavaBeans [28] or the CORBA Component Model [19] . These features are those needed to implement a distributed or a parallel program, that is they are mainly framework features and communication/interaction mechanisms. Concerning the framework mechanisms, we obviously need handy ways of both creating/instantiating and calling components across the different processing elements of the target architecture. We also need mechanisms and features that offer the programmer the possibility of controlling the parallel behavior of the Grid-aware application. In the Grid.it programming environment, we want to provide such mechanisms in the most abstract way possible. In particular, we want to leave the programmer the ability of concentrate on the functional behavior of the application, as well as on the qualitative aspects of parallelism exploitation. That is, we want to relieve the programmer of the responsibility of directly handling all the details related to the quantitative aspects of parallelism exploitation, and all those related to the usage of specific Grid middleware mechanisms. To understand the features of a high-performance components environment, it can be useful to distinguish three conceptual levels: a) computational model, b) functional and non-functional interfaces and c) support architecture for Gridaware applications. In this section, we start to deal with the first issue. The other ones are discussed in successive sections, where the Grid.it approach Components for High-Performance Grid Programming in Grid.it 5 based on ASSIST is presented. From the point of view of the computational model, we propose that high performance components are studied and characterized in terms of the following features: parallelism, component interaction, composition, and adaptivity. Parallelism. In general, components have an internal parallel structure (intracomponent parallelism). It must be possible to configure several, distinct versions of the same component, all versions having the same functional interfaces. Moving from one version to another one could be done by recompiling and/or reloading, in the most simple situations (static versions); however, we are interested also in parallel components that are able to change their internal structure/behaviour at run time (dynamic versions), depending on functional conditions (e.g. predicates on the computation state) and/or on non-functional conditions (e.g. variations in the achieved performance). In addition to intracomponent parallelism, the inter-component parallelism is fundamental for high-performance component applications as well. Component Interaction. Most component-based frameworks supply a way to declare the public services provided by a component and to invoke a service provided by a (remote) component. The mechanism is based on the uses/provides port abstraction. Being essentially a new edition of the RPC/RMI paradigm, this is sufficient to guarantee proper interactions between components, when they follow this simple client/server model. As an example, task farm computations (that is, embarrassingly parallel ones) can be implemented very efficiently using these mechanisms. However, different mechanisms are needed to implement other parallel patterns. For instance, pipelines cannot be easily expressed by means of the uses/provides port mechanism. Therefore, we assume that at least two distinct mechanisms are implemented: events, that is a way to register event handlers and to propagate events through the component network. This mechanism is already present in CCM. It can be exploited to implement all the typical asynchronous activities of parallel computations, such as monitoring. streams, that is a way to have uses/provides ports that implement dataflow-like channels for sequences of unidirectional typed communications, without incurring in the performance penalties related to the return messages and synchronizations typical of the plain uses/provides port mechanism. In general, a component has several input streams and several output streams, that can be used in a data-flow and/or in a nondeterministic fashion. A rich set of interaction mechanisms, which are typical of the parallel computation models, 6 is fundamental also in order to implement higher-level abstractions, such as complex workflow-based PSEs. Composition. Currently available component models allow components to interact in several different ways. However, only a few of them (e.g. CCM with the assembly construct) consider component composition as a primitive operation. In our opinion, composition is fundamental to allow more and more complex parallelism exploitation patterns to be developed and provided to the user as components. As derived from our experiences with algorithmic skeletons, as soon as an efficient mechanism to exploit basic parallelism patterns is available (see [29] [30] ) then the need for nesting/composition mechanisms arises (see [14, 10] ). By exploiting pattern composition, new parallel patterns can be programmed, best suited to user's needs. Furthermore, by properly restricting the visibility of user-defined, composed parallel patterns, different degrees of programmability of parallel applications can be presented to different classes of users. In our context, we assume to design a structured, component-based programming environment, and we actually want to be able to exploit composition of components to provide new, non-primitive components supporting the development of Grid-aware parallel applications. In conclusion, we need to define complex computation structures by means of the parallel composition of parallel components. A composition of components can be defined and reused as a new component in more complex structures. We assume that a general, explicitly parallel structure is encapsulated into a component in order to create a basic parallel component. A Grid-aware application must be able to deal with heterogeneity and dynamicity in order to guarantee the specified level of performance, in spite of the variety of run-time events that can change resource availability. A component must be characterized by non-functional interfaces, related to the performance control, and by features that allow the programmer to specify how the computation adapts at run time. Moreover, these features have to be implemented efficiently at the run-time support level. A strong relationship exists between the four features stated above. They must be integrated consistently in a global approach, framework, or better, in a programming model for high performance Grid programming. In Grid.it, we use ASSIST as the programming model able to satisfy this requirement.  We introduce ASSIST as derived from the NOW/COW programming environment as the way to denote parallel, high-performance, component-based, Grid applications. We also discuss how already implemented ASSIST features match the requirements emerging from the previous Section discussion or can be exploited/improved to match such requirements. ASSIST programs are structured as generic graphs (identified by the generic keyword), where nodes are parallel or sequential modules and arcs represent typed streams of data/objects. No constraint is imposed to the form of graphs, though "structured" graphs, such as those typical of a classical skeleton model, are a notable class of cases that have efficient implementations. All the interactions that are of interest in the composition of high-performance components are implemented easily and efficiently with the ASSIST streams. Streams are inherently asynchronous, however RPC/RMI interactions can be emulated effectively. Parallel modules are expressed by a generic skeleton, called parmod. In this context, "generic" means that a parmod is a general-purpose construct that can be tailored, for each application, to specific instances of classical streamparallel and/or data-parallel skeletons, and also to new forms of regular and irregular parallelism. A parmod operates on multiple input streams and multiple output streams. Several distribution and collection strategies are provided for the input and output streams respectively. Moreover, input streams can be controlled in a data-flow or in a nondeterministic manner. Nondeterminism is important to model several instances of workflow structures, as well as interaction by events. The parallel computation expressed in a parmod is decomposed in sequential units assigned to abstract executors called virtual processors (VP). The parmod can have an explicitly defined internal state for the duration of the computation. This feature is important in many cases, for example in nondeterministic/reactive computations, as well as in many irregular and dynamic computations. As in any model for structured parallel programming, the parmod construct is characterized by the important property that the implementation model is parametric. This means that the realization of the run-time support is largely independent of the actual mapping of the virtual processors of parmod onto the real processors: this is true as far as it concerns the distribution of functions, the distribution of data, and the communication. In the same way, an instance of a parmod is characterized by a performance model, which is parametric with respect to the actual realization. In the structured parallel programming community, a large amount of performance models have been provided for many stream-parallel and data-parallel skeletons. In ASSIST, we exploit this experience in order to characterize the behaviour of a parmod in terms of the performance it can offer according to the actual mapping. In many cases, i.e. where the parametric behaviour is predictable, the performance model is recognizable at compile-time, while in other, more dynamic cases, the association of a performance model to the computation, expressed by a parmod, requires some annotation by the programmer and/or the knowledge of the past history of the system or application. All the performance models can be made available, in a sort of Performance Model Repository, to the strategies implemented by the compiler and to the run-time support. The "parametricity" feature (parametric implementation model and parametric performance model) is the basis for the implementation of adaptive strategies in high-performance Grid-aware applications. How this issue is dealt with in Grid.it will be discussed in detail in Sect. 1.4.1. The "genericity" of the parmod construct offers an interesting opportunity to express adaptive parallel computations by program. That is, the same parmod (the same collection of virtual processors, input and output streams, and state variables) can express different parallelism forms according to the value of the internal state or of the input values. For example, in the Divide & Conquer implementation of the C4.5 algorithm [18] , in different phases the Divide module has a data-parallel or a task-farm-like behaviour, in order to optimize the available parallelism in each phase of the computation. Because of the huge amount of data associated to the internal state, this flexible implementation in ASSIST is much more efficient than an equivalent version in which the data-parallel phase and the farm-like phase are expressed by different specific skeletons. In other words, ASSIST offers a powerful feature for expressing and implementing adaptive computations: the same computation can be expressed according to several alternative strategies. As we describe in Sect. 1.4.1, alternative strategies can be associated to values generated by the program at run-time, or they can be selected according to the actual performance values with respect to the performance contract. ASSIST modules can refer to external objects during any phase of the computation, i.e. to objects not defined by the ASSIST coordination language and, consequently, that are referred according to their specific interfaces/APIs. In addition to libraries and system facilities (I/O, file, data bases), current external objects in ASSIST are shared variables, CORBA remote objects, storage objects and data repositories. The existence of external objects is a further facility to express alternative strategies for adaptive computations. Components for High-Performance Grid Programming in Grid.it ASSIST provides full interoperability with CORBA: not only an ASSIST program can act as a client of a CORBA server, but, most significantly, an ASSIST program can be automatically compiled as a CORBA object with RMIlike synchronous invocations or with stream-like asynchronous data passing. It has been shown [31] that the overhead introduced by the program transformation is definitely acceptable for many parallel applications. This experience proves that interoperability features can be efficiently merged into the ASSIST model, in order to design applications as composition of components, some of which will eventually be parallel. We figured the road-map transforming ASSIST programs/modules to components as follows: first, we allow ASSIST modules to be encapsulated as components in existing, well known component frameworks; then we include in the component framework all the mechanisms needed to implement highperformance applications; eventually, we integrate the framework in such a way that parallel ASSIST components and existing legacy components can coexist in an high-performance parallel Grid application. Following this road-map, our current research [31] will produce the next version of ASSIST (2.0), where an ASSIST program, expressed either as a single ASSIST module or as a graph of parallel or sequential modules, is considered as a high-performance component which: a) can be composed using standard component frameworks, in addition to the native ASSIST mechanisms, b) exports non-functional interfaces and features automatic support to adaptive applications, which will be discussed in the next section. W.r.t. standard frameworks, we are experimenting several solutions based on Web Services (WS) and the CORBA Component Model (CCM). The implementation approach is similar to the one already adopted for CORBA 2 interoperability, i.e. the compiler generates bridge ASSIST modules, which support the various kind of component ports related to the functional interfaces, as well as ports related to the non functional interfaces. From the point of view of compositionality, the ASSIST based approach offers the following features: i) a component (either WS or CCM) encapsulates an ASSIST (sub)graph, ii) components can be composed according to ASSIST mechanisms or according to the mechanisms of the standard component framework adopted. In the first solution of point ii), two or more components, being ASSIST graphs, are composed by the generic construct, which describes the structure of the resulting ASSIST graph in terms of component modules and streams (and possibly external objects). The composed ASSIST program is automatically 10 compiled into a standard component. This solution can be adopted when the components are all (new or existing) ASSIST programs whose ASSIST source code is available. In the second solution of point ii), the programmer uses the interaction mechanisms of the component framework (ports) to compose two or more components. This approach is typically adopted when one or more of the components of the application are existing (legacy) components that have not been designed in ASSIST. According to what stated in previous sections, several critical points have to be addressed when we tackle adaptivity control in Grid-aware applications. In particular, non-functional interfaces and reconfiguration strategy and application management have to be taken into account. In this section, we will discuss how these features have been taken into account in the design of our prototype of the component-based parallel programming environment ASSIST 2.0. We assume that a Grid-aware application is a composition of high-performance components. That is, we restrict to the case where no legacy, non-parallel components are used in the application. Let us consider the case in which such components are ASSIST components (graphs of sequential modules and/or parmods), composed by means of the generic graph construct. In addition to functional interfaces, that are automatically generated at compile time (out of the ASSIST code), each component is characterized by non-functional interfaces. They are expressed as annotations in a proper formalism, which is translated by the compiler into a run-time representation based on XML. Such annotations convey information about performance contract, reconfiguration strategy, and allocation constraints. The template of an ASSIST component thus assumes the form shown in Fig. 1 . Performance Contract. Many parameters can be used to specify the performance level that is required for the application. In this paper, we refer to the processing bandwidth (service time) in stream-based computations, and/or to the completion time, which is significant also for non-stream computations. However, the following discussion is largely independent of the specific performance parameters adopted. The performance contract can be specified for the whole application and/or for every single component. If the required performance of every component is specified, the required performance of the whole application can be derived at compile time using the knowledge of the graph. For example, the methodology of queueing networks can be used, both in the case of asynchronous stream and in the case of RMI-like interaction. If only the whole application performance is specified, it is still possible to derive rough information at compile and run time on the performance of the single components, using profiling estimates and, most important, taking into account that an ASSIST component is a composition of ASSIST modules for each of which a performance model may be known on the basis of a Performance Model Repository. Additional information related to communication bandwidth and latency must be estimated; of course, the reliability of this information may not be very accurate. However it is exactly because of these and other inaccuracies, which are inherent of Grid platforms, that we need a support for adaptive Gridaware applications. Reconfiguration Strategy. For each component, the application designer specifies which way the component has to be restructured at run-time if and when the performance contract happens to be no longer satisfied. The reconfiguration strategy is basically expressed in ASSIST with the addition of some annotation. In Sect. 1.3.1 we saw that ASSIST allows the programmer to express alternative strategies (e.g. different parametric forms of parallelism) directly in the same program, when their activation depends on the values of some program variables (e.g. the internal state of a parmod). Moreover, the programmer can also specify that alternative strategies must be activated when the performance contract is violated. Let us consider the following example (Fig. 2) . 12 a) Component C1 is an interface towards a Grid memory hierarchy, that virtualizes and transforms data sets available on the Grid into two streams of objects, the first one (whose elements have an elementary type) is sent to C2, and the other (whose elements have array type) is sent to C3. C1 may be an existing component available on the Grid, mediated by an ASSIST program. b) C2 is a parallel component encapsulating an ASSIST program. The reconfiguration strategy of C2 specifies that "by default" C2 is a sequential module executing a certain function F; when the current performance level must be adjusted C2 is transformed into a farm computation whose workers execute the same function F. The actual number of workers will be determined parametrically at run-time, according to the performance model and to the current availability of resources. c) C3 is a parallel component encapsulating an ASSIST data-parallel program operating on each stream element of array type. As in the case of C2, the strategy of C3 specifies that its parallelism degree (i.e. the amount of real processors onto which the virtual processors are mapped) can be modified, if needed. d) C4 is a parallel component encapsulating an ASSIST program which, by default, is a sequential module, but it can be restructured into a parmod operating on the input stream according to a data-parallel or to a task farm style, depending on the values of the parmod state and on the input values themselves. Therefore, in this case the adaptation principle is applied at two levels: at the program level and at the run-time support level. e) C5 is a parallel component encapsulating an ASSIST program operating nondeterministically on the input values received from C3 or C4, and transforming the two streams into a data set. Let us assume that, at a certain time, some monitoring activity signals that C2 is becoming a bottleneck and that this causes a substantial degradation of performance of the whole application. C2 can be transformed into a version with suitable parallelism degree. In this case other components may have to be restructured (e.g. C4,C5) in order to guarantee the level of performance. As previously stated, this is possible according to a global strategy based on the knowledge of the application structure. When restructuring data-parallel components (C3), the strategy must be applied also to the re-distribution of the data constituting the internal state of a parmod. ASSIST components
In the frame of the project, it will be investigated an "innovative programming environments that i) support the programmers in all the activities related to parallelism exploitation, by providing some kind of structured primitives for parallelism exploitation; ii) allow to achieve full interoperability with existing software, both parallel and sequential, either available in source or in object form; iii) support and enforce reuse of already developed code in other applications" REF .
Components for high performance Grid programming in Grid.it
Proc. of the Workshop on Component Models and Systems for Grid Applications, CoreGRID series
Computer Science