Software Pipelined Execution of Stream Programs on GPUs

The StreamIt programming model has been proposed to exploit parallelism in streaming applications on general purpose multi-core architectures. This model allows programmers to specify the structure of a program as a set of filters that act upon data, and a set of communication channels between them. The StreamIt graphs describe task, data and pipeline parallelism which can be exploited on modern Graphics Processing Units (GPUs), as they support abundant parallelism in hardware. In this paper, we describe the challenges in mapping StreamIt to GPUs and propose an efficient technique to software pipeline the execution of stream programs on GPUs. We formulate this problem - both scheduling and assignment of filters to processors - as an efficient Integer Linear Program (ILP), which is then solved using ILP solvers. We also describe a novel buffer layout technique for GPUs which facilitates exploiting the high memory bandwidth available in GPUs. The proposed scheduling utilizes both the scalar units in GPU, to exploit data parallelism, and multiprocessors, to exploit task and pipelin parallelism. Further it takes into consideration the synchronization and bandwidth limitations of GPUs, and yields speedups between 1.87X and 36.83X over a single threaded CPU.

Simplified theory of optical nonlinearities in spin-polarized bulk GaAs

Apart from their intrinsic physical interest, spin-polarized many-body effects are expected to be important to the working of spintronic devices. A vast literature exists on the effects of a spin-unpolarized electron-hole plasma on the optical properties of a semiconductor. Here, we include the spin degree of freedom to model optical absorption of circularly polarized light by spin-polarized bulk GaAs. Our model is easy to implement and does not require elaborate numerics, since it is based on the closed-form analytical pair-equation formula that is valid in 3d. The efficacy of our approach is demonstrated by a comparison with recent experimental data.

Robust heuristics for scalable optimization of complex SQL queries

Modern database systems incorporate a query optimizer to identify the most efficient "query execution plan" for executing the declarative SQL queries submitted by users. A dynamic-programming-based approach is used to exhaustively enumerate the combinatorially large search space of plan alternatives and, using a cost model, to identify the optimal choice. While dynamic programming (DP) works very well for moderately complex queries with up to around a dozen base relations, it usually fails to scale beyond this stage due to its inherent exponential space and time complexity. Therefore, DP becomes practically infeasible for complex queries with a large number of base relations, such as those found in current decision-support and enterprise management applications. To address the above problem, a variety of approaches have been proposed in the literature. Some completely jettison the DP approach and resort to alternative techniques such as randomized algorithms, whereas others have retained DP by using heuristics to prune the search space to computationally manageable levels. In the latter class, a well-known strategy is "iterative dynamic programming" (IDP) wherein DP is employed bottom-up until it hits its feasibility limit, and then iteratively restarted with a significantly reduced subset of the execution plans currently under consideration. The experimental evaluation of IDP indicated that by appropriate choice of algorithmic parameters, it was possible to almost always obtain "good" (within a factor of twice of the optimal) plans, and in the few remaining cases, mostly "acceptable" (within an order of magnitude of the optimal) plans, and rarely, a "bad" plan. While IDP is certainly an innovative and powerful approach, we have found that there are a variety of common query frameworks wherein it can fail to consistently produce good plans, let alone the optimal choice. This is especially so when star or clique components are present, increasing the complexity of th- e join graphs. Worse, this shortcoming is exacerbated when the number of relations participating in the query is scaled upwards.

Scouts, Promoters, and Connectors: The Roles of Ratings in Nearest-Neighbor Collaborative Filtering

Recommender systems aggregate individual user ratings into predictions of products or services that might interest visitors. The quality of this aggregation process crucially affects the user experience and hence the effectiveness of recommenders in e-commerce. We present a characterization of nearest-neighbor collaborative filtering that allows us to disaggregate global recommender performance measures into contributions made by each individual rating. In particular, we formulate three roles-scouts, promoters, and connectors-that capture how users receive recommendations, how items get recommended, and how ratings of these two types are themselves connected, respectively. These roles find direct uses in improving recommendations for users, in better targeting of items and, most importantly, in helping monitor the health of the system as a whole. For instance, they can be used to track the evolution of neighborhoods, to identify rating subspaces that do not contribute ( or contribute negatively) to system performance, to enumerate users who are in danger of leaving, and to assess the susceptibility of the system to attacks such as shilling. We argue that the three rating roles presented here provide broad primitives to manage a recommender system and its community.

Selective dissemination of XML documents based on genetically learned user model and Support Vector Machines

Extensible Markup Language ( XML) has emerged as a medium for interoperability over the Internet. As the number of documents published in the form of XML is increasing, there is a need for selective dissemination of XML documents based on user interests. In the proposed technique, a combination of Adaptive Genetic Algorithms and multi class Support Vector Machine ( SVM) is used to learn a user model. Based on the feedback from the users, the system automatically adapts to the user's preference and interests. The user model and a similarity metric are used for selective dissemination of a continuous stream of XML documents. Experimental evaluations performed over a wide range of XML documents, indicate that the proposed approach significantly improves the performance of the selective dissemination task, with respect to accuracy and efficiency.

Simplified theory of optical nonlinearities in spin-polarized bulk GaAs

Apart from their intrinsic physical interest, spin-polarized many-body effects are expected to be important to the working of spintronic devices. A vast literature exists on the effects of a spin-unpolarized electron-hole plasma on the optical properties of a semiconductor. Here, we include the spin degree of freedom to model optical absorption of circularly polarized light by spin-polarized bulk GaAs. Our model is easy to implement and does not require elaborate numerics, since it is based on the closed-form analytical pair-equation formula that is valid in 3d. The efficacy of our approach is demonstrated by a comparison with recent experimental data.

Phase behavior of concentrated aqueous solutions of cetyltrimethylammonium bromide (CTAB) and sodium hydroxy naphthoate (SHN)

We have characterized the phase behavior of mixtures of the cationic surfactant cetyltrimethylammonium bromide (CTAB) and the organic salt 3-sodium-2-hydroxy naphthoate (SHN) over a wide range of surfactant concentrations using polarizing optical microscopy and X-ray diffraction. A variety of liquid crystalline phases, such as hexagonal, lamellar with and without curvature defects, and nematic, are observed in these mixtures. At high temperatures the curvature defects in the lamellar phase are annealed gradually on decreasing the water content. However, at lower temperatures these two lamellar structures are separated by an intermediate phase, where the bilayer defects appear to order into a lattice. The ternary phase diagram shows a high degree of symmetry about the line corresponding to equimolar CTAB/SHN composition, as in the case of mixtures of cationic and anionic surfactants.

Volume change behaviour of fine grained solis

Soils in and and semi-arid zones undergoes volume changes due to wetting. Depending upon the type of clay minerals present, degree of saturation, externally applied load and bonding, the fine grained soils either swells or compresses. One of the parameter that affects the volume change behaviour is the primary clay mineral present in their clay size fraction. A simple method of identifying the same has been presented. It has been brought out that in an expansive unsaturated undisturbed soil, the diffuse double layer repulsion, the stress state and the bonding play significant role in their volume change behaviour. In non-expansive fine grained unsaturated undisturbed soils, the shearing resistance at particle level (including the matrix suction and bonding) and fabric play a significant role in influencing the volume change behaviour. While both the mechanism co-exist, one of them play a dominant role depending upon the primary clay mineral is swelling or non swelling.

Exploring the interaction energies for the binding of hydroxydiphenyl ethers to enoyl-acyl carrier protein reductases

It is now well established that the potent anti-microbial compound, triclosan, interrupts the type II fatty acid synthesis by inhibiting the enzyme enoyl-ACP reductase in a number of organisms. Existence of a high degree of similarity between the recently discovered enoyl-ACP reductase from R falciparum and B. napus enzyme permitted building of a satisfactory model for the former enzyme that explained some of the key aspects of the enzyme such as its specificity for binding to the cofactor and the inhibitor. We now report the interaction energies between triclosan and other hydroxydiphenyl ethers with the enzymes from B. napus, E. coli and R falciparum. Examination of the triclosan-enzyme interactions revealed that subtle differences exist in the ligand binding sites of the enzymes from different sources i.e., B. napus, E. coli and P falciparum. A comparison of their binding propensities thus determined should aid in the design of effective inhibitors for the respective enzymes.