Non-uniform data distribution for communication-efficient parallel clustering

Global communicationrequirements andloadimbalanceof someparalleldataminingalgorithms arethe major obstacles to exploitthe computational power of large-scale systems. This work investigates how non-uniform data distributions can be exploited to remove the global communication requirement and to reduce the communication costin parallel data mining algorithms and, in particular, in the k-means algorithm for cluster analysis. In the straightforward parallel formulation of the k-means algorithm, data and computation loads are uniformly distributed over the processing nodes. This approach has excellent load balancing characteristics that may suggest it could scale up to large and extreme-scale parallel computing systems. However, at each iteration step the algorithm requires a global reduction operationwhichhinders thescalabilityoftheapproach.Thisworkstudiesadifferentparallelformulation of the algorithm where the requirement of global communication is removed, while maintaining the same deterministic nature ofthe centralised algorithm. The proposed approach exploits a non-uniform data distribution which can be either found in real-world distributed applications or can be induced by means ofmulti-dimensional binary searchtrees. The approachcanalso be extended to accommodate an approximation error which allows a further reduction ofthe communication costs. The effectiveness of the exact and approximate methods has been tested in a parallel computing system with 64 processors and in simulations with 1024 processing element

A fast two-grid and finite section method for a class of integral equations on the real line with application to an acoustic scattering problem in the half-plane

We consider the numerical treatment of second kind integral equations on the real line of the form ∅(s) = ∫_(-∞)^(+∞)▒〖κ(s-t)z(t)ϕ(t)dt,s=R〗 (abbreviated ϕ= ψ+K_z ϕ) in which K ϵ L_1 (R), z ϵ L_∞ (R) and ψ ϵ BC(R), the space of bounded continuous functions on R, are assumed known and ϕ ϵ BC(R) is to be determined. We first derive sharp error estimates for the finite section approximation (reducing the range of integration to [-A, A]) via bounds on (1-K_z )^(-1)as an operator on spaces of weighted continuous functions. Numerical solution by a simple discrete collocation method on a uniform grid on R is then analysed: in the case when z is compactly supported this leads to a coefficient matrix which allows a rapid matrix-vector multiply via the FFT. To utilise this possibility we propose a modified two-grid iteration, a feature of which is that the coarse grid matrix is approximated by a banded matrix, and analyse convergence and computational cost. In cases where z is not compactly supported a combined finite section and two-grid algorithm can be applied and we extend the analysis to this case. As an application we consider acoustic scattering in the half-plane with a Robin or impedance boundary condition which we formulate as a boundary integral equation of the class studied. Our final result is that if z (related to the boundary impedance in the application) takes values in an appropriate compact subset Q of the complex plane, then the difference between ϕ(s)and its finite section approximation computed numerically using the iterative scheme proposed is ≤C_1 [kh log⁡〖(1⁄kh)+(1-Θ)^((-1)⁄2) (kA)^((-1)⁄2) 〗 ] in the interval [-ΘA,ΘA](Θ<1) for kh sufficiently small, where k is the wavenumber and h the grid spacing. Moreover this numerical approximation can be computed in ≤C_2 N log⁡N operations, where N = 2A/h is the number of degrees of freedom. The values of the constants C1 and C2 depend only on the set Q and not on the wavenumber k or the support of z.

The physical pendulum in an advanced undergraduate course in mechanics

The physical pendulum treated with a Hamiltonian formulation is a natural topic for study in a course in advanced classical mechanics. For the past three years, we have been offering a series of problem sets studying this system numerically in our third-year undergraduate courses in mechanics. The problem sets investigate the physics of the pendulum in ways not easily accessible without computer technology and explore various algorithms for solving mechanics problems. Our computational physics is based on Mathematica with some C communicating with Mathematica, although nothing in this paper is dependent on that choice. We have nonetheless found this system, and particularly its graphics, to be a good one for use with undergraduates.

FAMOUS, faster: using parallel computing techniques to accelerate the FAMOUS/HadCM3 climate model with a focus on the radiative transfer algorithm

We have optimised the atmospheric radiation algorithm of the FAMOUS climate model on several hardware platforms. The optimisation involved translating the Fortran code to C and restructuring the algorithm around the computation of a single air column. Instead of the existing MPI-based domain decomposition, we used a task queue and a thread pool to schedule the computation of individual columns on the available processors. Finally, four air columns are packed together in a single data structure and computed simultaneously using Single Instruction Multiple Data operations. The modified algorithm runs more than 50 times faster on the CELL’s Synergistic Processing Elements than on its main PowerPC processing element. On Intel-compatible processors, the new radiation code runs 4 times faster. On the tested graphics processor, using OpenCL, we find a speed-up of more than 2.5 times as compared to the original code on the main CPU. Because the radiation code takes more than 60% of the total CPU time, FAMOUS executes more than twice as fast. Our version of the algorithm returns bit-wise identical results, which demonstrates the robustness of our approach. We estimate that this project required around two and a half man-years of work.

Achieving market segmentation from B2B sectorisation

Purpose – The creation of a target market strategy is integral to developing an effective business strategy. The concept of market segmentation is often cited as pivotal to establishing a target market strategy, yet all too often business-to-business marketers utilise little more than trade sectors or product groups as the basis for their groupings of customers, rather than customers' characteristics and buying behaviour. The purpose of this paper is to offer a solution for managers, focusing on customer purchasing behaviour, which evolves from the organisation's existing criteria used for grouping its customers. Design/methodology/approach – One of the underlying reasons managers fail to embrace best practice market segmentation is their inability to manage the transition from how target markets in an organisation are currently described to how they might look when based on customer characteristics, needs, purchasing behaviour and decision-making. Any attempt to develop market segments should reflect the inability of organisations to ignore their existing customer group classification schemes and associated customer-facing operational practices, such as distribution channels and sales force allocations. Findings – A straightforward process has been derived and applied, enabling organisations to practice market segmentation in an evolutionary manner, facilitating the transition to customer-led target market segments. This process also ensures commitment from the managers responsible for implementing the eventual segmentation scheme. This paper outlines the six stages of this process and presents an illustrative example from the agrichemicals sector, supported by other cases. Research implications – The process presented in this paper for embarking on market segmentation focuses on customer purchasing behaviour rather than business sectors or product group classifications - which is true to the concept of market segmentation - but in a manner that participating managers find non-threatening. The resulting market segments have their basis in the organisation's existing customer classification schemes and are an iteration to which most managers readily buy-in. Originality/value – Despite the size of the market segmentation literature, very few papers offer step-by-step guidance for developing customer-focused market segments in business-to-business marketing. The analytical tool for assessing customer purchasing deployed in this paper originally was created to assist in marketing planning programmes, but has since proved its worth as the foundation for creating segmentation schemes in business marketing, as described in this paper.

Estimation of visual motion parameters used for bio-inspired navigation

Visual motion cues play an important role in animal and humans locomotion without the need to extract actual ego-motion information. This paper demonstrates a method for estimating the visual motion parameters, namely the Time-To-Contact (TTC), Focus of Expansion (FOE), and image angular velocities, from a sparse optical flow estimation registered from a downward looking camera. The presented method is capable of estimating the visual motion parameters in a complicated 6 degrees of freedom motion and in real time with suitable accuracy for mobile robots visual navigation.

Efficient group communication for large-scale parallel clustering

Global communication requirements and load imbalance of some parallel data mining algorithms are the major obstacles to exploit the computational power of large-scale systems. This work investigates how non-uniform data distributions can be exploited to remove the global communication requirement and to reduce the communication cost in iterative parallel data mining algorithms. In particular, the analysis focuses on one of the most influential and popular data mining methods, the k-means algorithm for cluster analysis. The straightforward parallel formulation of the k-means algorithm requires a global reduction operation at each iteration step, which hinders its scalability. This work studies a different parallel formulation of the algorithm where the requirement of global communication can be relaxed while still providing the exact solution of the centralised k-means algorithm. The proposed approach exploits a non-uniform data distribution which can be either found in real world distributed applications or can be induced by means of multi-dimensional binary search trees. The approach can also be extended to accommodate an approximation error which allows a further reduction of the communication costs.

Analysis of incoherent scatter radar data from non-thermal F-region plasma

A procedure is presented for fitting incoherent scatter radar data from non-thermal F-region ionospheric plasma, using theoretical spectra previously predicted. It is found that values of the shape distortion factor D∗, associated with deviations of the ion velocity distribution from a Maxwellian distribution, and ion temperatures can be deduced (the results being independent of the path of iteration) if the angle between the line-of-sight and the geomagnetic field is larger than about 15–20°. The procedure can be used with one or both of two sets of assumptions. These concern the validity of the adopted model for the line-of-sight ion velocity distribution in the one case or for the full three-dimensional ion velocity distribution function in the other. The distribution function employed was developed to describe the line-of-sight velocity distribution for large aspect angles, but both experimental data and Monte Carlo simulations indicate that the form of the field-perpendicular distribution can also describe the distribution at more general aspect angles. The assumption of this form for the line-of-sight velocity distribution at a general aspect angle enables rigorous derivation of values of the one-dimensional, line-of-sight ion temperature. With some additional assumptions (principally that the field-parallel distribution is always Maxwellian and there is a simple relationship between the ion temperature anisotropy and the distortion of the field-perpendicular distribution from a Maxwellian), fits to data for large aspect angles enable determination of line-of-sight temperatures at all aspect angles and hence, of the average ion temperature and the ion temperature anisotropy. For small aspect angles, the analysis is restricted to the determination of the line-of-sight ion temperature because the theoretical spectrum is insensitive to non-thermal effects when the plasma is viewed along directions almost parallel to the magnetic field. This limitation is expected to apply to any realistic model of the ion velocity distribution function and its consequences are discussed. Fit strategies which allow for mixed ion composition are also considered. Examples of fits to data from various EISCAT observing programmes are presented.

Analysis of incoherent scatter spectra from non-Maxwellian plasma

Incoherent scatter data from non-thermal F-region ionospheric plasma are analysed, using theoretical spectra predicted by Raman et al. It is found that values of the semi-empirical drift parameter D∗, associated with deviations of the ion velocity distribution from a Maxwellian, and the plasma temperatures can be rigorously deduced (the results being independent of the path of iteration) if the angle between the line-of-sight and the geomagnetic field is larger than about 15–20 degrees. For small aspect angles, the deduced value of the average (or 3-D) ion temperature remains ambiguous and the analysis is restricted to the determination of the line-of-sight temperature because the theoretical spectrum is insensitive to non-thermal effects when the plasma is viewed along directions almost parallel to the magnetic field. This limitation is expected to apply to any realistic model of the ion velocity distribution, and its consequences are discussed. Fit strategies which allow for mixed ion composition are also considered. Examples of fits to data from various EISCAT observing programmes are presented.

Quantifying the role of biosphere-atmosphere feedbacks in climate change: coupled model simulation for 6000 years B.P. and comparison with palaeodata for northern Eurasia and northern Africa

The LMD AGCM was iteratively coupled to the global BIOME1 model in order to explore the role of vegetation-climate interactions in response to mid-Holocene (6000 y BP) orbital forcing. The sea-surface temperature and sea-ice distribution used were present-day and CO2 concentration was pre-industrial. The land surface was initially prescribed with present-day vegetation. Initial climate “anomalies” (differences between AGCM results for 6000 y BP and control) were used to drive BIOME1; the simulated vegetation was provided to a further AGCM run, and so on. Results after five iterations were compared to the initial results in order to identify vegetation feedbacks. These were centred on regions showing strong initial responses. The orbitally induced high-latitude summer warming, and the intensification and extension of Northern Hemisphere tropical monsoons, were both amplified by vegetation feedbacks. Vegetation feedbacks were smaller than the initial orbital effects for most regions and seasons, but in West Africa the summer precipitation increase more than doubled in response to changes in vegetation. In the last iteration, global tundra area was reduced by 25% and the southern limit of the Sahara desert was shifted 2.5 °N north (to 18 °N) relative to today. These results were compared with 6000 y BP observational data recording forest-tundra boundary changes in northern Eurasia and savana-desert boundary changes in northern Africa. Although the inclusion of vegetation feedbacks improved the qualitative agreement between the model results and the data, the simulated changes were still insufficient, perhaps due to the lack of ocean-surface feedbacks.

Modelling primary producer interaction and composition: an example of a UK lowland river

Nutrient enrichment and drought conditions are major threats to lowland rivers causing ecosystem degradation and composition changes in plant communities. The controls on primary producer composition in chalk rivers are investigated using a new model and existing data from the River Frome (UK) to explore abiotic and biotic interactions. The growth and interaction of four primary producer functional groups (suspended algae, macrophytes, epiphytes, sediment biofilm) were successfully linked with flow, nutrients (N, P), light and water temperature such that the modelled biomass dynamics of the four groups matched that of the observed. Simulated growth of suspended algae was limited mainly by the residence time of the river rather than in-stream phosphorus concentrations. The simulated growth of the fixed vegetation (macrophytes, epiphytes, sediment biofilm) was overwhelmingly controlled by incoming solar radiation and light attenuation in the water column. Nutrients and grazing have little control when compared to the other physical controls in the simulations. A number of environmental threshold values were identified in the model simulations for the different producer types. The simulation results highlighted the importance of the pelagic–benthic interactions within the River Frome and indicated that process interaction defined the behaviour of the primary producers, rather than a single, dominant driver. The model simulations pose interesting questions to be considered in the next iteration of field- and laboratory based studies.

The diffusion of the Transition Network in four European countries

The Transition Network exemplifies the potential of social movements to create spaces of possibility for alternatives to emerge in the interstices of mainstream, neoliberal economies. Yet, little work has been carried out so far on the Transition Network or other grassroots innovations for sustainability in a way that reveals their actual patterns of diffusion. This graphic of the diffusion of the Transition Network visualises its spatial structure and compare diffusion patterns across Italy, France, Great Britain and Germany. The graphics show that the number of transition initiatives in the four countries has steadily increased over the past eight years, but the rate of increase has slowed down in all countries. The maps clearly show that in all four countries the diffusion of the Transition Network has not been spatially even. The graphic suggests that in each country transition initiatives are more likely to emerge in some geographical areas (hotspots) than in others (cold spots). While the existence of a spatial structure of the Transition Network may result from the combination of place-specific factors and diffusion mechanisms, these graphics illustrate the importance of better comprehending where grassroots innovations emerge.

MOLES3: implementing an ISO standards driven data catalogue

ISO19156 Observations and Measurements (O&M) provides a standardised framework for organising information about the collection of information about the environment. Here we describe the implementation of a specialisation of O&M for environmental data, the Metadata Objects for Linking Environmental Sciences (MOLES3). MOLES3 provides support for organising information about data, and for user navigation around data holdings. The implementation described here, “CEDA-MOLES”, also supports data management functions for the Centre for Environmental Data Archival, CEDA. The previous iteration of MOLES (MOLES2) saw active use over five years, being replaced by CEDA-MOLES in late 2014. During that period important lessons were learnt both about the information needed, as well as how to design and maintain the necessary information systems. In this paper we review the problems encountered in MOLES2; how and why CEDA-MOLES was developed and engineered; the migration of information holdings from MOLES2 to CEDA-MOLES; and, finally, provide an early assessment of MOLES3 (as implemented in CEDA-MOLES) and its limitations. Key drivers for the MOLES3 development included the necessity for improved data provenance, for further structured information to support ISO19115 discovery metadata export (for EU INSPIRE compliance), and to provide appropriate fixed landing pages for Digital Object Identifiers (DOIs) in the presence of evolving datasets. Key lessons learned included the importance of minimising information structure in free text fields, and the necessity to support as much agility in the information infrastructure as possible without compromising on maintainability both by those using the systems internally and externally (e.g. citing in to the information infrastructure), and those responsible for the systems themselves. The migration itself needed to ensure continuity of service and traceability of archived assets.