Automatic parallel code generation for message passing on distributed memory systems

The availability of a very accurate dependence graph for a scalar code is the basis for the automatic generation of an efficient parallel implementation. The strategy for this task which is encapsulated in a comprehensive data partitioning code generation algorithm is described. This algorithm involves the data partition, calculation of assignment ranges for partitioned arrays, addition of a comprehensive set of execution control masks, altering loop limits, addition and optimisation of communications for all data. In this context, the development and implementation of strategies to merge communications wherever possible has proved an important feature in producing efficient parallel implementations for numerical mesh based codes. The code generation strategies described here are embedded within the Computer Aided Parallelisation tools (CAPTools) software as a key part of a toolkit for automating as much as possible of the parallelisation process for mesh based numerical codes. The algorithms used enables parallelisation of real computational mechanics codes with only minor user interaction and without any prior manual customisation of the serial code to suit the parallelisation tool.

Three parallel programming paradigms: Comparisons on an archetypal PDE computation

Three paradigms for distributed-memory parallel computation that free the application programmer from the details of message passing are compared for an archetypal structured scientific computation -- a nonlinear, structured-grid partial differential equation boundary value problem -- using the same algorithm on the same hardware. All of the paradigms -- parallel languages represented by the Portland Group's HPF, (semi-)automated serial-to-parallel source-to-source translation represented by CAP-Tools from the University of Greenwich, and parallel libraries represented by Argonne's PETSc -- are found to be easy to use for this problem class, and all are reasonably effective in exploiting concurrency after a short learning curve. The level of involvement required by the application programmer under any paradigm includes specification of the data partitioning, corresponding to a geometrically simple decomposition of the domain of the PDE. Programming in SPMD style for the PETSc library requires writing only the routines that discretize the PDE and its Jacobian, managing subdomain-to-processor mappings (affine global-to-local index mappings), and interfacing to library solver routines. Programming for HPF requires a complete sequential implementation of the same algorithm as a starting point, introduction of concurrency through subdomain blocking (a task similar to the index mapping), and modest experimentation with rewriting loops to elucidate to the compiler the latent concurrency. Programming with CAPTools involves feeding the same sequential implementation to the CAPTools interactive parallelization system, and guiding the source-to-source code transformation by responding to various queries about quantities knowable only at runtime. Results representative of "the state of the practice" for a scaled sequence of structured grid problems are given on three of the most important contemporary high-performance platforms: the IBM SP, the SGI Origin 2000, and the CRAYY T3E.

CAPLib - A 'thin layer' message passing library to support computational mechanics codes on distributed memory parallel systems

The Computer Aided Parallelisation Tools (CAPTools) [Ierotheou, C, Johnson SP, Cross M, Leggett PF, Computer aided parallelisation tools (CAPTools)-conceptual overview and performance on the parallelisation of structured mesh codes, Parallel Computing, 1996;22:163±195] is a set of interactive tools aimed to provide automatic parallelisation of serial FORTRAN Computational Mechanics (CM) programs. CAPTools analyses the user's serial code and then through stages of array partitioning, mask and communication calculation, generates parallel SPMD (Single Program Multiple Data) messages passing FORTRAN. The parallel code generated by CAPTools contains calls to a collection of routines that form the CAPTools communications Library (CAPLib). The library provides a portable layer and user friendly abstraction over the underlying parallel environment. CAPLib contains optimised message passing routines for data exchange between parallel processes and other utility routines for parallel execution control, initialisation and debugging. By compiling and linking with different implementations of the library, the user is able to run on many different parallel environments. Even with today's parallel systems the concept of a single version of a parallel application code is more of an aspiration than a reality. However for CM codes the data partitioning SPMD paradigm requires a relatively small set of message-passing communication calls. This set can be implemented as an intermediate `thin layer' library of message-passing calls that enables the parallel code (especially that generated automatically by a parallelisation tool such as CAPTools) to be as generic as possible. CAPLib is just such a `thin layer' message passing library that supports parallel CM codes, by mapping generic calls onto machine specific libraries (such as CRAY SHMEM) and portable general purpose libraries (such as PVM an MPI). This paper describe CAPLib together with its three perceived advantages over other routes: - as a high level abstraction, it is both easy to understand (especially when generated automatically by tools) and to implement by hand, for the CM community (who are not generally parallel computing specialists); - the one parallel version of the application code is truly generic and portable; - the parallel application can readily utilise whatever message passing libraries on a given machine yield optimum performance.

Two-machine shop scheduling: Compromise between flexibility and makespan value

In this paper, we consider the problem of providing flexibility to solutions of two-machine shop scheduling problems. We use the concept of group-scheduling to characterize a whole set of schedules so as to provide more choice to the decision-maker at any decision point. A group-schedule is a sequence of groups of permutable operations defined on each machine where each group is such that any permutation of the operations inside the group leads to a feasible schedule. Flexibility of a solution and its makespan are often conflicting, thus we search for a compromise between a low number of groups and a small value of makespan. We resolve the complexity status of the relevant problems for the two-machine flow shop, job shop and open shop. A number of approximation algorithms are developed and their worst-case performance is analyzed. For the flow shop, an effective heuristic algorithm is proposed and the results of computational experiments are reported.

Assessment of the nutritional value of wild leafy vegetables consumed in the Buhera District of Zimbabwe: a preliminary study

Wild leafy vegetables play a vital role in the livelihoods of many communities in Africa. The focus of this study was to investigate the nutritional value of wild vegetables commonly consumed by the people of Buhera District in the Manicaland province of Zimbabwe. A variety of vegetables including Amaranthus hybridus, Cleome gynandra, Bidens pilosa, Corchorus tridens, and Adansonia digitata were collected during a survey in Buhera District. Samples were processed employing traditional methods of cooking and drying, then subjected to proximate and micronutrient analyses. The results indicate that these vegetables were particularly high in calcium, iron, and vitamin C. Compared with Brassica napus (rape), Amaranthus hybridus contained twice the amount of calcium, with other nutrients almost in the same range. Compared with Spinacia oleracea (spinach), Amaranthus hybridus contained three times more vitamin C (44 mg/100 g). Calcium levels were 530 mg/100 g. Amaranthus hybridus was also found to contain 7, 13, and 20 times more vitamin C, calcium, and iron respectively compared with Lactuca sativa (lettuce). Cleome gynandra contained 14 mg/100 g, 115 mg/100 g, 9 mg/100 g of vitamin C, calcium, and iron respectively. Bidens pilosa was found to be a valuable source of vitamin C (63 mg/100 g), iron (15 mg/100 g), and zinc (19 mg/100 g), compared with Brassica oleracea (cabbage). The leaves of Corchorus tridens were an excellent source of vitamin C (78 mg/100 g), calcium (380 mg/100 g), and iron (8 mg/100 g). The Adansonia digitata leaves were also rich in vitamin C (55 mg/100 g), iron (23 mg/ 100 g), and calcium (400 mg/100 g). Based on these nutrient contents, the above vegetables will have potential benefits as part of feeding programmes, as well as their promotion as part of composite diet for vulnerable groups.

What is the value of technology? Toward a labour theory of technology change

Economic analysis of technology treats it as given exogenously, while determined endogenously. This paper examines the conceptual conflict. The paper outlines an alternative conceptual framework. This uses a 'General Vertical Division of Labour' into conceptual and executive parts to facilitate a coherent political economic explanation of technological change. The paper suggests that we may acquire rather than impose an understanding of technological change. It also suggests that we may re-define and reassess the efficiency of technological change, through the values inculcated into it.

An inquiry concerning the acceptance of intrinsic value theories of nature

This study empirically assesses the extent to which intrinsic value theories of nature are accepted and acknowledged outside the realm of academic environmental ethics. It focuses on twenty of the largest landowning organisations in England, including both conservation and non-conservation organisations and investigates the environmental philosophical beliefs and values held by representative individuals of these groups. An in-depth interview was held with a representative from each organisation. The interviews were analysed using qualitative data analysis software and the results compared against a backdrop of academic philosophical positions. The study found that an ecocentric position which acknowledges nature's intrinsic value was adopted by the majority of respondents, both from conservation and non-conservation organisations. However, it was also found that individuals felt the idea of nature's intrinsic value was generally not reflected in organisational policy.