Abstract We outline the design of a recommendation system (MyPYTHIA) implemented as a Web portal. MyPYTHIA's design objectives include evaluating the quality and performance of scientific software on Grid platforms, creating knowledge about which software and computational services should be selected for solving particular problems, selecting parameters of software (or of computational services) based on user‐specified computational objectives, providing access to performance data and knowledge bases over the Web and enabling recommendations for targeted application domains. MyPYTHIA uses a combination of statistical analysis, pattern extraction techniques and a database of software performance to map feature‐based representations of problem instances to appropriate software. MyPYTHIA's open architecture allows the user to customize it for conducting individual case studies. We describe the architecture as well as several scientific domains of knowledge enabled by such case studies. Copyright © 2002 John Wiley & Sons, Ltd.

The simulation and modeling of complex physical systems often involves many components because (i) the physical system itself has components of differing natures, (ii) parallel computing strategies require many (somewhat independent) components, and (iii) existing simulation software applies only to simpler geometrical shapes and physical situations. We discuss how agent based networks are applied to such multi-component applications. The network agents are used to (a) control the execution of existing solvers on sub-components, (b) mediate between sub-components, and (c) coordinate the execution of the ensemble. This paper focuses on partial differential equation (PDE) models as an instance of the approach and describes the implementation of networks using the PELLPACK problem solving environment for PDEs and the Bond system for agent based computing. Copyright © 2000 John Wiley & Sons, Ltd.

Often scientists need to locate appropriate software for their problems and then select from among many alternatives. We have previously proposed an approach for dealing with this task by processing performance data of the targeted software. This approach has been tested using a customized implementation referred to as PYTHIA. This experience made us realize the complexity of the algorithmic discovery of knowledge from performance data and of the management of these data together with the discovered knowledge. To address this issue, we created PYTHIA-II—a modular framework and system which combines a general knowledge discovery in databases (KDD) methodology and recommender system technologies to provide advice about scientific software/hardware artifacts. The functionality and effectiveness of the system is demonstrated for two existing performance studies using sets of software for solving partial differential equations. From the end-user perspective, PYTHIA-II allows users to specify the problem to be solved and their computational objectives. In turn, PYTHIA-II (i) selects the software available for the user's problem (ii) suggests parameter values, and (iii) assesses the recommendation provided. PYTHIA-II provides all the necessary facilities to set up database schemas for testing suites and associated performance data in order to test sets of software. Moreover, it allows easy interfacing of alternative data mining and recommendation facilities. PYTHIA-II is an open-ended system implemented on public domain software and has been used for performance evaluation in several different problem domains.

The POEMS project is creating an environment for end-to-end performance modeling of complex parallel and distributed systems, spanning the domains of application software, runtime and operating system software, and hardware architecture. Toward this end, the POEMS framework supports composition of component models from these different domains into an end-to-end system model. This composition can be specified using a generalized graph model of a parallel system, together with interface specifications that carry information about component behaviors and evaluation methods. The POEMS Specification Language compiler will generate an end-to-end system model automatically from such a specification. The components of the target system may be modeled using different modeling paradigms and at various levels of detail. Therefore, evaluation of a POEMS end-to-end system model may require a variety of evaluation tools including specialized equation solvers, queuing network solvers, and discrete event simulators. A single application representation based on static and dynamic task graphs serves as a common workload representation for all these modeling approaches. Sophisticated parallelizing compiler techniques allow this representation to be generated automatically for a given parallel program. POEMS includes a library of predefined analytical and simulation component models of the different domains and a knowledge base that describes performance properties of widely used algorithms. The paper provides an overview of the POEMS methodology and illustrates several of its key components. The modeling capabilities are demonstrated by predicting the performance of alternative configurations of Sweep3D, a benchmark for evaluating wavefront application technologies and high-performance, parallel architectures.

The article presents the software architecture and implementation of the problem-solving environment (PSE) PELLPACK for modeling physical objects described by partial differential equations (PDEs). The scope of this PSE is broad, as PELLPACK incorporates many PDE solving systems, and some of these, in turn, include several specific PDE solving methods. Its coverage for 1D, 2D. and 3D elliptic or parabolic problems is quite broad, and it handles some hyperbolic problems, Since a PSE should provided complete support for the problem-solving process, PELLPACK also contains a large amount of code to support graphical user interfaces, analystic tools, user help, domain or mesh partitioning, machine and data selection, visualization, and various other tasks. Its total size is well over 1 million lines code. Its open-ended software architecture consists of several software layers. The top layer is an interactive graphical interface for specifying the PDE model and its solution framework This interface saves that results of the user specification in the form of a very high level PDE language which is an alternative interface to the PELLPACK system. This language also allows a user to specify the PDE problem and its solution framework textually in a natural form. The PELLPACK language preprocessor generates a Fortran control program with the interfaces, calls to specified components and libraries of the PDE solution framework, and functions defining the PDE problem. The PELLPACK program execution is supported by a hign-level tool where the virtual parallel system is defined, where the compilation, loading, and execution are controlled. Finally, the PELLPACK PSE integrates several PDE libraries and PDE systems based on the decomposition of discrete geometric data to map sparse PDE computations to parallel machines. An instance of the system is available as aWeb server(WebPELLPACK) for public use at http://pellpack.cs.purdue.edu.

Advances in wired and wireless networking technologies are making networked computing the most common form of high performance computing. Similarly, software like Mosaic and Netscape have not only unified the networked computing landscape, but they have made it available to the masses in a simple, machine independent way. These developments are changing the way we do computational science, learn, research, collaborate, access information and resources, and maintain local and global relations. We envision a scenario where large scale computational science and engineering applications like virtual classrooms and laboratories are ubiquitous, and information resources are accessible on-demand from anywhere. In this paper we present the design of a user interface that will be appropriate to this scenario. We argue that interfaces modeled on the pen and paper paradigm are suited in this context. Specifically, we present the software architecture of a notebook interface. We lay down the requirements for such an interface and present its implementation using the World Wide Web. A realization of the notebook model is presented for a problem solving environment (PDELab) to support the numerical simulation of PDE based applications on a network of heterogeneous high performance machines. © 1997 John Wiley & Sons, Ltd.

Problem-solving e*nvironments (PSEs) interact with the user in a language “natural” to the associated discipline, and they provide a high-level abstraction of the underlying, computationally complex model. The knowledge-based system PYTHIA addresses the problem of (parameter, algorithm) pair selection within a scientific computing domain assuming some minimum user-specified computational objectives and some characteristics of the given problem. PYTHIA's framework and methodology are general and applicable to any class of scientific problems and solvers. PYTHIA is applied in the context of Parallel ELLPACK where there are many alternatives for the numerical solution of elliptic partial differential equations (PDEs). PYTHIA matches the characteristics of the given problem with those of PDEs in an existing problem population and then uses performance profiles of the various solvers to select the appropriate method given user-specified error and solution time bounds. The profiles are automatically generated for each solver of the Parallel ELLPACK library.— Authors' Abstract

Problem solving using complex mathematical models of physical phenomena requires expert knowledge in a variety of fields of computer science, such as parallel computing and numerical methods. SciAgents is a problem-solving environment to allow these models to become truly easy to use for the application scientists, much like PC-based systems. It is based on the agent-oriented model of computing. In this paper, we discuss the design and architecture of SciAgents in the context of models based on partial differential equations. We present a set of artificial/computational intelligence techniques used by the cooperating agents that constitute SciAgents, which allows them to complete the program specification and to carry out the program execution with minimal need for user intervention. SciAgents permits the non-expert user to cost-effectively and easily develop software for solving complex mathematical models. It is scalable and allows for extensive reuse of existing software.

We consider computations associated with data parallel iterative solvers used for the numerical solution of partial differential equations (PDEs). The mapping of such computations into load balanced tasks requiring minimum synchronization and communication is a difficult combinatorial optimization problem. Its optimal solution is essential for the efficient parallel processing of PDE computations. Determining data mappings that optimize a number of criteria, like workload balance, synchronization, and local communication, often involves the solution of an NP-Complete problem. Although data mapping algorithms have been known for a few years, there is lack of qualitative and quantitative comparisons based on the actual performance of the parallel computation. In this paper we present two new data mapping algorithms and evaluate them together with a large number of existing ones using the actual performance of data parallel iterative PDE solvers on the nCUBE II. Comparisons on the performance of data parallel iterative PDE solvers on medium and large scale problems demonstrate that some computationally inexpensive data block partitioning algorithms are as effective as the computationally expensive deterministic optimization algorithms. Also, these comparisons demonstrate that the existing approach in solving the data partitioning problem is inefficient for large scale problems. Finally, a software environment for the solution of the partitioning problem of data parallel iterative solvers is presented.

Abstract The paper discusses algorithms and programs for electron density averaging using a distributed memory MIMD system. Electron density averaging is a computationally intensive step needed for phase refinement and extension in the computation of the 3‐D structure of macromolecules like proteins and viruses. The determination of a single structure may require thousands of hours of CPU time for traditional supercomputers. The approach discussed in this paper leads to a reduction by one to two orders of magnitude of the computing time. The program runs on an Intel iPSC/860 and on the Touchstone Delta system and uses a user controlled shared virtual memory and a dynamic load‐balancing mechanism.

Abstract Synchronization is a major cause of wasted computing cycles and of diminished performance in parallel computing. This paper investigates the effects of synchronization upon the performance of iterative methods on distributed memory MIMD machines. A quantitative analysis of the effects of the communication latency and of the load imbalance due to the non‐deterministic execution times for iterative methods is presented. This analysis explains the rather poor performance observed often in actual implementations of such methods and suggests better ways to achieve convergence without frequent synchronization.

In this paper we study the partitioning and allocation of computations associated with the numerical solution of partial differential equations (PDEs). Strategies for the mapping of such computations to parallel MIMD architectures can be applied to different levels of the solution process. We introduce and study heuristic approaches defined on the associated geometric data structures (meshes). Specifically, we study methods for decomposing finite element and finite difference meshes into balanced, nonoverlapping subdomains which guarantee minimum communication and synchronization among the underlying associated subcomputations. Two types of algorithms are considered: clustering techniques based on sequential orderings of the discrete geometric data and optimization based techniques involving geometric or graphical metric criteria. These algorithms support the automatic mode of a geometry decomposition tool developed in the parallel ELLPACK environment which is implemented under X11-window systems. A brief description of this tool is presented.

In the parallel ELLPACK (//ELLPACK) project we are developing a library of parallel interative methods for distributed memory multiprocessor systems and software tools for partitioning and allocation of the underlying computations. In this paper we discuss the implementation issues within the //ELLPACK environment and present preliminary performance results of some of the modules on three hypercube based architectures: NCUBE, iPSC/1 and iPSC/2. These results indicate that the iterative methods are capable of delivering close to optimal scaled speed-ups while the combination of concurrent/vector processing can lead to sizable improvements of the overall performance. These experiments have shown that distributed memory systems are capable of solving significantly large problems effectively.

We consider the integration of a domain decomposition technique with a new quadratic spline collocation discretization scheme for solving second order elliptic boundary value problems on rectangles. The domain decomposition method is based on the capacitance matrix technique. Due to the limitations of existing methods for solving the corresponding capacitance problem, we develop and analyze iterative methods for its solution. The optimum partitioning and mapping of the underlying computation is studied on hypercube architectures. A numerical realization of this method is presented on NCUBE/7 (128 processors) and its comparative efficiency is measured. The resulting parallel quadratic spline collocation-capacitance method is seen to be efficient in achieving accurate solutions and in using parallel architectures.

We consider the collocation method for linear, second-order elliptic problems on rectangular and general two-dimensional domains. An overview of the method is given for general domains, followed by a discussion of the improved efficiencies and simplifications possible for rectangular domains. A very-high-level description is given of three specific collocation algorithms that use Hermite bicubic basic functions, (1) GENCOL (collocation on general two-dimensional domains), (2) HERMCOL (collocation on rectangular domains with general linear boundary conditions), and (3) INTCOL (collocation on rectangular domains with uncoupled boundary conditions). The linear system resulting from INTCOL has half the bandwidth of that from HERMCOL, which provides substantial benefit in solving the system. We provide some examples showing the range of applicability of the algorithms and some performance profiles illustrating their efficiency. Fortran implementations of these algorithms are given in the companion papers [10, 11].

article Free AccessArtifacts AvailableArtifacts Evaluated & Reusable Share on Algorithm 637: GENCOL: collocation of general domains with bicubic hermite polynomials Authors: E. N. Houstis Purdue Univ. and Univ. of Thessaloniki Purdue Univ. and Univ. of ThessalonikiView Profile , W. F. Mitchell Purdue Univ. Purdue Univ.View Profile , J. R. Rice Purdue Univ. Purdue Univ.View Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 11Issue 4Dec. 1985 pp 413–415https://doi.org/10.1145/6187.6194Published:01 December 1985Publication History 13citation376DownloadsMetricsTotal Citations13Total Downloads376Last 12 Months8Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

article Free AccessArtifacts AvailableArtifacts Evaluated & Reusable Share on Algorithm 638: INTCOL and HERMCOL: collocation on rectangular domains with bicubic hermite polynomials Authors: E. N. Houstis Purdue Univ. and Univ. of Thessaloniki Purdue Univ. and Univ. of ThessalonikiView Profile , W. F. Mitchell Purdue Univ. Purdue Univ.View Profile , J. R. Rice Purdue Univ. Purdue Univ.View Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 11Issue 4Dec. 1985 pp 416–418https://doi.org/10.1145/6187.6195Online:01 December 1985Publication History 14citation374DownloadsMetricsTotal Citations14Total Downloads374Last 12 Months10Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Consider a bounded two-dimensional domain R with boundary OR.Applications that involve processing R include approximation, numerical integration, and the numerical solution of partial differential equations.In each case the geometric information of R and OR must be put into a data structure (either implicitly or explicitly) as an initial phase of the problem solution.This paper presents one approach to this problem based on overlaying R by a rectangular grid.R is assumed to be defined by parameterization of pieces of OR plus an orientation.Specific representations of this information are given, and a data structure that is convenient for using the geometric information in various applications is presented.An algorithm to produce this information is given in a companion paper, "Algorithm xxx: A Two-Dimensional Domain Processor"; various special techniques of the algorithm are described.The application to numerical integration is discussed in some detail.

This algorithm uses a large number of heuristics, and it is impractical (if not impossible) to precisely define those domains for which the algorithm is intended to work.A careful reading of the companion paper [1] reveals many of the assumptions used; we list the more important ones here.(1) The domain has more than two or three interior grid points.(2) The boundary does not enter a grid element several times.(3) The boundary is fairly smooth on the scale of the grid.(4) The coordinates and parameters of the problem are all ordinary-sized numbers.(5) The parameterization of the boundary pieces is made by smooth, monotonic, and well-behaved functions.(6) There are no corners on the boundary except at the ends of boundary pieces.(7) Holes, if any, are separated so that there is always an interior grid point between boundaries of different subdomains and the main domain.(8) The interior grid points of the domain are connected through the grid.(9) The grid is reasonably uniform.Most of these assumptions are automatically satisfied if the grid is fine enough.

THE MACROPROCESSORA macroprocessor is a tool for substituting values from a symbol table into a text.Thus, if DATE has the value 'JULY 10, 1983' and PLACE has the value 'HONG KONG', then the text fragment DATELINE: $DATE, $PLACE.

No abstract available.

We describe a fast metalgonthm for adaptive quadrature on a MIMD (Multiple Instruction, Multiple Data) parallel computer and show that its speedup ts at least constant times M/log M using a total of M processors

This paper describes a system to systematically compare the performance of various methods (software modules) for the numerical solution of partial differential equations. We discuss the general nature and large size of this performance evaluation problem and the data one obtains. The system meets certain design objectives that ensure a valid experiment: 1) precise definition of a particular measurement; 2) uniformity in defimition of variables entering the experiment; and 3) reproducibility of results. The ease of use of the system makes it possible to make the large sets of measurements necessary to obtain confidence in the results and its portability allows others to check or extend the measurements. The system has four parts: 1) semiautomatic generation of problems for experimental input; 2) the ELLPACK system for actually solving the equation; 3) a data management system to organize and access the experimental data; and 4) data analysis programs to extract graphical and statistical summaries from the data.

article Free AccessArtifacts AvailableArtifacts Evaluated & Reusable Share on Algorithm 525: ADAPT, Adaptive Smooth Curve Fitting [E2] Author: John R. Rice Department of Computer Science, Purdue University, Lafayette, IN Department of Computer Science, Purdue University, Lafayette, INView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 4Issue 1March 1978 pp 82–94https://doi.org/10.1145/355769.355777Online:01 March 1978Publication History 11citation600DownloadsMetricsTotal Citations11Total Downloads600Last 12 Months16Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This is the third in a sequence of papers on parallel algorithms for adaptive quadrature.The primary aim is to study the rate of convergence achieved by such algorithms.Here we prove that a specific algorithm (computer program) achieves the optimal rate of convergence which has been established by the previous papers.More specifically, under certain reasonable hypotheses, it is proved that this program terminates with a quadrature estimate within the prescribed input accuracy requirement and that this estimate is computed with a number of integrand evaluations of a specified order as the accuracy requirement goes to zero.Since operational parallel computers are still rare, the program is given in a pseudo-Fortran for a hypothetical true (multiple instruction stream, multiple data stream) parallel computer.A simulation shows that this algorithm has a reasonable speed-up, although it is not optimal in this paper.

No abstract available.

The few adaptive quadrature algorithms that have appeared are significantly superior to traditional numerical integration algorithms The concept of metalgorithm is introduced to provide a framework for the systematic study of the range of interesting adaptive quadrature algorithms A principal result is that there are from i to 10 million potentially interesting and distinct algorithms This is followed by a considerable development of metalgorithm analysis.In partmular, theorems about the convergence properties of various classes of algorithms are established which theoretically show the experimentally observed superiority of these algorithms.Roughly, these theorems state.(a) for "well-behaved" integrands adaptive algorithms are just as efficient and effective as traditional algorithms of a "comparable" nature, (b) adaptive algorithms are equally effective for "badly behaved" integrands where traditional ones are ineffective The final part of the paper introduces the concept of a characteristic length and its role is illustrated in an analyms of three concrete realizations of the metalgorithm, including the algorithms CADRE and SQUANK KEY WORDS AND PHRASES' quadrature, numerical Integration, adaptive quadrature, quadrature convergence, numerical integration convergence, numermal integration programs, quadrature data structures, algorithm classes, algorithm analyms, algorithm components CR CATEGORIES' 3.62, 5.16, 5.29 IntroductwnThe quadrature problem for a given function f(x) is to estimate the value of If = f'0f(x) dx.Traditional quadrature formulas give estimates of the form N Q~f = ~ w~f(xd for some suitably chosen weights w, and abscissas x,.Adaptive quadrature uses some algorithm to choose the abscissas and weights during the computation and thus is to dynamically adapt its estimate to the particular properties of the integrand f(x).A number of adaptive quadrature algorithms have appeared in the literature [2,6,8,9] and there is some basis [3,5] to believe that they are significantly superior to traditional quadrature formulas.As shown later, the few algorithms that have appeared only scratch the surface of the possibilities, and one purpose of this paper is to systematically study the range of interesting adaptive quadrature algorithms.The concept of metalgorithm is introduced for this purpose; the word means a framework or theory to study algorithms.Webster's relevant definition of the prefix "met" is "discipline designed to deal critically with the original one."

The primary purpose of the ACM Transactions on Mathematical Software (TOMS) is to expand the opportunities to publish important results concerning mathematical software and significant computer programs.There is no intention to compete with existing journals (including ACM's own journal) which publish theoretical results in numerical analysis and mathematical computing.The publication of algorithms in TOMS replaces the algorithms department of Communications of the ACM, and ACM's looseleaf service "Collected Algorithms from ACM" (formerly "from CACM") (CALGO) will have the same relationship to TOMS that it has had with that algorithms department.From the top-down view of science, TOMS is partially on the top, abstract level and partially on the second, more concrete level.The top level, for example, is represented by fundamental research papers on the analysis and critical evaluation of computer programs; the second level is represented by practically oriented, concrete research and development in traditional areas like linear algebra, polynomial manipulation, and nonlinear programming.There has been very little outlet for such work and TOMS is to provide it.The definition of the scope of a new journal is a critical, point.Unfortunately, there is little consensus on just what "mathematical software" means: some clearly mathematical problems (e.g.sorting, searching, program proofs) are currently considered to be in the province of other specialities of computer science; some areas (e.g. program dissemination and maintenance) included in the scope of TOMS are clearly not mathematical.We may consider the scope from two viewpoints, one vertical and one horizontal.In either case there is to be heavy emphasis on practical and applications oriented work.A key requirement for papers in TOMS is that they support significant areas of computer application.The vertical definition of the scope of TOMS involves seven levels of abstraction and applicability:

The ACM Algorithm Distribution Service makes it possible to remove the length limitation on algorithms published in TOMS and allows TOMS to publish and disseminate large programs.Technically, a collection of algorithms is just another algorithm, but practically ACM editors will distinguish between "ordinary" algorithms and larger entities called polyalgorithms, software packages, systemized collections, etc.This policy statement is an extension of the algorithms policy of TOMS which describes those software packages that TOMS is interested in publishing and gives the specific requirements expected for such a package.

This book is the proceedings of a symposium held at the IBM T. J. Watson Research Center in March 1972. It contains the 14 papers presented plus an account of the panel discussion session. There was considerable attention given in the panel discussion to the field of the symposium. There was no agreement on a suitable name although "computational complexity," "computability," "theory of algorithms," and "concrete computational complexity" were suggested. Neither was there good agreement on the content of the field, but the symposium (and this book) itself serve admirably to delineate the field. That is, the content of this field (whatever it is called) is that which the people in the fleld are doing.