A sequential algorithm for sparse support vector classifiers

Support vector machines (SVMs), though accurate, are not preferred in applications requiring high classification speed or when deployed in systems of limited computational resources, due to the large number of support vectors involved in the model. To overcome this problem we have devised a primal SVM method with the following properties: (1) it solves for the SVM representation without the need to invoke the representer theorem, (2) forward and backward selections are combined to approach the final globally optimal solution, and (3) a criterion is introduced for identification of support vectors leading to a much reduced support vector set. In addition to introducing this method the paper analyzes the complexity of the algorithm and presents test results on three public benchmark problems and a human activity recognition application. These applications demonstrate the effectiveness and efficiency of the proposed algorithm.


--------------------------------------------------------------------------------

Minimal Hilbert series for quadratic algebras and the Anick conjecture

We study the question on whether the famous Golod–Shafarevich estimate, which gives a lower bound for the Hilbert series of a (noncommutative) algebra, is attained. This question was considered by Anick in his 1983 paper ‘Generic algebras and CW-complexes’, Princeton Univ. Press, where he proved that the estimate is attained for the number of quadratic relations $d\leq n^2/4$
and $d\geq n^2/2$, and conjectured that it is the case for any number of quadratic relations. The particular point where the number of relations is equal to $n(n-1)/2$ was addressed by Vershik. He conjectured that a generic algebra with this number of relations is finite dimensional. We announce here the result that over any infinite field, the Anick conjecture holds for $d \geq 4(n2+n)/9$ and an arbitrary number of generators. We also discuss the result that confirms the Vershik conjecture over any field of characteristic 0, and a series of related
asymptotic results.

Finite dimensional semigroup quadratic algebras with the minimal number of relations

A quadratic semigroup algebra is an algebra over a field given by the generators x_1, . . . , x_n and a finite set of quadratic relations each of which either has the shape x_j x_k = 0 or the shape x_j x_k = x_l x_m . We prove that a quadratic semigroup algebra given by n generators and d=(n^2+n)/4 relations is always infinite dimensional. This strengthens the Golod–Shafarevich estimate for the above class of algebras. Our main result however is that for every n, there is a finite dimensional quadratic semigroup algebra with n generators and d_n relations, where d_n is the first integer greater than (n^2+n)/4 . That is, the above Golod–Shafarevich-type estimate for semigroup algebras is sharp.

Embedded C programming: a practical course introducing programmable microprocessors

This paper presents a new laboratory-based module for embedded systems teaching, which addresses the current lack of consideration for the link between hardware development, software implementation, course content and student evaluation in a laboratory environment. The course introduces second year undergraduate students to the interface between hardware and software and the programming of embedded devices; in this case, the PIC (originally peripheral interface controller, later rebranded programmable intelligent computer) microcontroller. A hardware development board designed for use in the laboratories of this module is presented. Through hands on laboratory experience, students are encouraged to engage with practical problem-solving exercises and develop programming skills across a broad range of scenarios.

Constraint rule-based programming of norms for electronic institutions

Norms constitute a powerful coordination mechanism among heterogeneous agents. In this paper, we propose a rule language to specify and explicitly manage the normative positions of agents (permissions, prohibitions and obligations), with which distinct deontic notions and their relationships can be captured. Our rule-based formalism includes constraints for more expressiveness and precision and allows to supplement (and implement) electronic institutions with norms. We also show how some normative aspects are given computational interpretation. © 2008 Springer Science+Business Media, LLC.

Strategies for Energy-Efficient Resource Management of Hybrid Programming Models

Many scientific applications are programmed using hybrid programming models that use both message passing and shared memory, due to the increasing prevalence of large-scale systems with multicore, multisocket nodes. Previous work has shown that energy efficiency can be improved using software-controlled execution schemes that consider both the programming model and the power-aware execution capabilities of the system. However, such approaches have focused on identifying optimal resource utilization for one programming model, either shared memory or message passing, in isolation. The potential solution space, thus the challenge, increases substantially when optimizing hybrid models since the possible resource configurations increase exponentially. Nonetheless, with the accelerating adoption of hybrid programming models, we increasingly need improved energy efficiency in hybrid parallel applications on large-scale systems. In this work, we present new software-controlled execution schemes that consider the effects of dynamic concurrency throttling (DCT) and dynamic voltage and frequency scaling (DVFS) in the context of hybrid programming models. Specifically, we present predictive models and novel algorithms based on statistical analysis that anticipate application power and time requirements under different concurrency and frequency configurations. We apply our models and methods to the NPB MZ benchmarks and selected applications from the ASC Sequoia codes. Overall, we achieve substantial energy savings (8.74 percent on average and up to 13.8 percent) with some performance gain (up to 7.5 percent) or negligible performance loss.

Autonomic management of non-functional concerns in distributed & parallel application programming

An approach to the management of non-functional concerns in massively parallel and/or distributed architectures that marries parallel programming patterns with autonomic computing is presented. The necessity and suitability of the adoption of autonomic techniques are evidenced. Issues arising in the implementation of autonomic managers taking care of multiple concerns and of coordination among hierarchies of such autonomic managers are discussed. Experimental results are presented that demonstrate the feasibility of the approach.

Field observation of sequestration of uranium in iron-rich sediments under sequential reduction-oxidation conditions at the DOE Oak Ridge IFRC

At the U.S. DOE Oak Ridge Integrated Field Research Challenge (ORIFRC) site, the iron content of shallow subsurface materials (i.e. weathered saprolite) is relatively high (up to 5-6% as w/w), and therefore, the forms of the iron species present plays a critical role in the long-term sequestration of uranium. A long term pilot-scale study of the bioreduction and reoxidation of uranium conducted at the ORIFRC area 3 site, adjacent to the former S-3 disposal ponds (source zone), has provided us with the opportunity to study the impact of iron species on the sequestration of U(VI). The aqueous U(VI) concentrations at the site were decreased to below the EPA MCL through the intermittent injection of ethanol as the electron donor. Previous field tests indicated that both oxygen and nitrate could oxidize the bioreduced U(IV) and cause a short-term rebound of aqueous phase uranium concentration after the oxidative agents were delivered directly to the bioreduced zone.

A field test has been conducted to examine the long-term effect of exposure of bioreduced sediments to nitrate in contaminated groundwater for more than 1,380 days at the Area 3 site. Contaminated groundwater was allowed to invade the previously bioreduced zone via the natural groundwater gradient after an extended period in which reducing conditions were maintained and the bioreduced zone was protected from the influx of upgradient contaminated groundwater. The geochemical response to the invasion of contaminated groundwater was dependent on whether the monitoring location is in the middle or the fringe of the previously bioreduced zone. In general, the nitrate concentrations in the previously bioreduced area, increased gradually from near zero to ~50-300 mM within 200 days and then stabilized. The pH declined from bioreduced levels of 6.2-6.7 to below 5.0. Uranium concentrations rebounded in all monitoring wells but at different rates. At most locations U concentrations rebounded, declined and then rebounded again. Methane gas disappeared while a significant level (20,000 to 44,000 ppmv) N2O was found in the groundwater of monitoring wells after three years of reoxidization.

The U(IV) in sediments was mainly reoxidized to U(VI) species. Based on XANES analysis, the predominate uranium in all samples after re-oxidation was similar to a uranyl nitrate form. But the U content in the sediment remained as high as that determined after bioreduction activates were completed, indicating that much of the U is still sequestrated in situ. SEM observations of surged fine sediments revealed that clusters of colloidal-sized (200-500nm) U-containing precipitates appeared to have formed in situ, regardless from sample of FW106 in non-bioactivity control area or of pre-bioreduced FW101-2 and FW102-3. Additionally, SEM-EDS and microprobe analysis, showed that the U-containing precipitates (~1% U) in FW106 are notably higher in Fe, compared to the precipitates (~1-2.5% U) from FW101-2 and FW102-3. However, XRF analysis indicated that the U content was remained as high as 2180 and 1810 mg/kg with U/Fe ratio at 0.077 and 0.055 vs 0.037 g/g, respectively in pre-bioreduced FW101-2 and FW102-3, suggesting more U sequestrated by Fe in pre-bioreduced sediments.

Selectable linear or quadratic coupling in an optomechanical system

There has been much interest recently in the analysis of optomechanical systems incorporating dielectric nano- or microspheres inside a cavity field. We analyse here the situation when one of the mirrors of the cavity itself is also allowed to move. We reveal that the interplay between the two oscillators yields a cross-coupling that results in, e.g., appreciable cooling and squeezing of the motion of the sphere, despite its nominal quadratic coupling. We also discuss a simple modification that would allow this cross-coupling to be removed at will, thereby yielding a purely quadratic coupling for the sphere.

A language-independent parallel refactoring framework

Recent trends towards increasingly parallel computers mean that there needs to be a seismic shift in programming practice. The time is rapidly approaching when most programming will be for parallel systems. However, most programming techniques in use today are geared towards sequential, or occasionally small-scale parallel, programming. While refactoring has so far mainly been applied to sequential programs, it is our contention that refactoring can play a key role in significantly improving the programmability of parallel systems, by allowing the programmer to apply a set of well-defined transformations in order to parallelise their programs. In this paper, we describe a new language-independent refactoring approach that helps introduce and tune parallelism through high-level design patterns targeting a set of well-specified parallel skeletons. We believe this new refactoring process is the key to allowing programmers to truly start thinking in parallel. © 2012 ACM.

Accelerating code on multi-cores with FastFlow

FastFlow is a programming framework specifically targeting cache-coherent shared-memory multi-cores. It is implemented as a stack of C++ template libraries built on top of lock-free (and memory fence free) synchronization mechanisms. Its philosophy is to combine programmability with performance. In this paper a new FastFlow programming methodology aimed at supporting parallelization of existing sequential code via offloading onto a dynamically created software accelerator is presented. The new methodology has been validated using a set of simple micro-benchmarks and some real applications. © 2011 Springer-Verlag.

Parallel Programming

Recent trends in computing systems, such as multi-core processors and cloud computing, expose tens to thousands of processors to the software. Software developers must respond by introducing parallelism in their software. To obtain highest performance, it is not only necessary to identify parallelism, but also to reason about synchronization between threads and the communication of data from one thread to another. This entry gives an overview on some of the most common abstractions that are used in parallel programming, namely explicit vs. implicit expression of parallelism and shared and distributed memory. Several parallel programming models are reviewed and categorized by means of these abstractions. The pros and cons of parallel programming models from the perspective of performance and programmability are discussed.

A Comparison of Programming Models for Multiprocessors with Explicitly Managed Memory Hierarchies

On multiprocessors with explicitly managed memory hierarchies (EMM), software has the responsibility of moving data in and out of fast local memories. This task can be complex and error-prone even for expert programmers. Before we can allow compilers to handle the complexity for us, we must identify the abstractions that are general enough to allow us to write applications with reasonable effort, yet speci?c enough to exploit the vast on-chip memory bandwidth of EMM multi-processors. To this end, we compare two programming models against hand-tuned codes on the STI Cell, paying attention to programmability and performance. The ?rst programming model, Sequoia, abstracts the memory hierarchy as private address spaces, each corresponding to a parallel task. The second, Cellgen, is a new framework which provides OpenMP-like semantics and the abstraction of a shared address spaces divided into private and shared data. We compare three applications programmed using these models against their hand-optimized counterparts in terms of abstractions, programming complexity, and performance.

Enabling science through emerging HPC technologies: accelerating numerical quadrature using a GPU

The R-matrix method when applied to the study of intermediate energy electron scattering by the hydrogen atom gives rise to a large number of two electron integrals between numerical basis functions. Each integral is evaluated independently of the others, thereby rendering this a prime candidate for a parallel implementation. In this paper, we present a parallel implementation of this routine which uses a Graphical Processing Unit as a co-processor, giving a speedup of approximately 20 times when compared with a sequential version. We briefly consider properties of this calculation which make a GPU implementation appropriate with a view to identifying other calculations which might similarly benet.