Implementation of parallel tridiagonal solvers for a heterogeneous computing environment

Tridiagonal diagonally dominant linear systems arise in many scientific and engineering applications. The standard Thomas algorithm for solving such systems is inherently serial forming a bottleneck in computation. Algorithms such as cyclic reduction and SPIKE reduce a single large tridiagonal system into multiple small independent systems which can be solved in parallel. We have developed portable cyclic reduction and SPIKE algorithm OpenCL implementations with the intent to target a range of co-processors in a heterogeneous computing environment including Field Programmable Gate Arrays (FPGAs), Graphics Processing Units (GPUs) and other multi-core processors. In this paper, we evaluate these designs in the context of solver performance, resource efficiency and numerical accuracy.

Parallel polygon scan conversion algorithms: Performance evaluation on a shared bus architecture

In this paper, three parallel polygon scan conversion algorithms have been proposed, and their performance when executed on a shared bus architecture has been compared. It has been shown that the parallel algorithm that does not use edge coherence performs better than those that use edge coherence. Further, a multiprocessing architecture has been proposed to execute the parallel polygon scan conversion algorithms more efficiently than a single shared bus architecture.

A parallel-serial binary arbitration scheme for collision-free multi-access techniques

Multi-access techniques are widely used in computer networking and distributed multiprocessor systems. On-the-fly arbitration schemes permit one of the many contenders to access the medium without collisions. Serial arbitration is cost effective but is slow and hence unsuitable for high-speed multiprocessor environments supporting very high data transfer rates. A fully parallel arbitration scheme takes less time but is not practically realisable for large numbers of contenders. In this paper, a generalised parallel-serial scheme is proposed which significantly reduces the arbitration time and is practically realisable.

Parallel packing of alpha-helices in crystals of the zervamicin IIA analog Boc-Trp-Ile-Ala-Aib-Ile-Val-Aib-Leu-Aib-Pro-OMe.2H2O.

An apolar synthetic analog of the first 10 residues at the NH2-terminal end of zervamicin IIA crystallizes in the triclinic space group P1 with cell dimensions a = 10.206 +/- 0.002 A, b = 12.244 +/- 0.002 A, c = 15.049 +/- 0.002 A, alpha = 93.94 +/- 0.01 degrees, beta = 95.10 +/- 0.01 degrees, gamma = 104.56 +/- 0.01 degrees, Z = 1, C60H97N11O13 X 2H2O. Despite the relatively few alpha-aminoisobutyric acid residues, the peptide maintains a helical form. The first intrahelical hydrogen bond is of the 3(10) type between N(3) and O(0), followed by five alpha-helix-type hydrogen bonds. Solution 1H NMR studies in chloroform also favor a helical conformation, with seven solvent-shielded NH groups. Continuous columns are formed by head-to-tail hydrogen bonds between the helical molecules along the helix axis. The absence of polar side chains precludes any lateral hydrogen bonds. Since the peptide crystallizes with one molecule in a triclinic space group, aggregation of the helical columns must necessarily be parallel rather than antiparallel. The packing of the columns is rather inefficient, as indicated by very few good van der Waals' contacts and the occurrence of voids between the molecules.

A parallel wilf algorithm for complex zeros of a polynomial

A global recursive bisection algorithm is described for computing the complex zeros of a polynomial. It has complexityO(n 3 p) wheren is the degree of the polynomial andp the bit precision requirement. Ifn processors are available, it can be realized in parallel with complexityO(n 2 p); also it can be implemented using exact arithmetic. A combined Wilf-Hansen algorithm is suggested for reduction in complexity.

Note on the stability of parallel magnetic fields

The stability characteristics of parallel magnetic fields when fluid motions are present along the lines of force is studied. The stability criterion for both symmetric (m=0) and asymmetric (m=1) modes are discussed and the results obtained by Trehan and Singh (1978) are amended in the present study. The results obtained for the cylindrical geometry are shown to play an important role forka<4, wherek is the wave number,a is the radius of the cylinder, compared to the results obtained by Geronicolas (1977) for the slab geometry.

Natural frequencies of rectangular orthotropic plates with a pair of parallel edges simply supported

Solutions of the exact characteristic equations for the title problem derived earlier by an extension of Bolotin's asymptotic method are considered. These solutions, which correspond to flexural modes with frequency factor, R, greater than unity, are expressed in convenient forms for all combinations of clamped, simply supported and free conditions at the remaining pair of parallel edges. As in the case of uniform beams, the eigenvalues in the CC case are found to be equal to those of elastic modes in the FF case provided that the Kirchoff's shear condition at a free edge is replaced by the condition. The flexural modes with frequency factor less than unity are also investigated in detail by introducing a suitable modification in the procedure. When Poisson's ratios are not zero, it is shown that the frequency factor corresponding to the first symmetric mode in the free-free case is less than unity for all values of side ratio and rigidity ratios. In the case of one edge clamped and the other free it is found that modes with frequency factor less than unity exist for certain dimensions of the plate—a fact hitherto unrecognized in the literature.

Novel Biginelli dihydropyrimidines with potential anticancer activity: A parallel synthesis and CoMSIA study

Novel Biginelli dihydropyrimidines of biological interest were prepared using p-toluene sulphonic acid as an efficient catalyst. All the thirty-two synthesised dihydropyrimidines were evaluated for their in vitro antioxidant activity using DPPH method. Only, compounds 28 and 29 exhibited reasonably good antioxidant activity. Furthermore, the synthesised Biginelli compounds were subjected for their in vitro anticancer activity against MCF-7 human breast cancer cells. The title compounds were tested at the concentration of 10 μg. Compounds exhibited activity ranging from weak to moderate and, from moderate to high in terms of percentage cytotoxicity. Among them, compounds 10 and 11 exhibited significant anticancer activity. In order to elucidate the three-dimensional structure–activity relationships (3D QSAR) towards their anticancer activity, we subjected them for comparative molecular similarity indices analysis (CoMSIA). Illustration regarding their synthesis, analysis, antioxidant activity, anticancer activity and 3D QSAR study is described.

Inflammation-driven bone formation in a mouse model of ankylosing spondylitis: Sequential not parallel processes

Background Ankylosing spondylitis (AS) is an immune-mediated arthritis particularly targeting the spine and pelvis and is characterised by inflammation, osteoproliferation and frequently ankylosis. Current treatments that predominately target inflammatory pathways have disappointing efficacy in slowing disease progression. Thus, a better understanding of the causal association and pathological progression from inflammation to bone formation, particularly whether inflammation directly initiates osteoproliferation, is required. Methods The proteoglycan-induced spondylitis (PGISp) mouse model of AS was used to histopathologically map the progressive axial disease events, assess molecular changes during disease progression and define disease progression using unbiased clustering of semi-quantitative histology. PGISp mice were followed over a 24-week time course. Spinal disease was assessed using a novel semi-quantitative histological scoring system that independently evaluated the breadth of pathological features associated with PGISp axial disease, including inflammation, joint destruction and excessive tissue formation (osteoproliferation). Matrix components were identified using immunohistochemistry. Results Disease initiated with inflammation at the periphery of the intervertebral disc (IVD) adjacent to the longitudinal ligament, reminiscent of enthesitis, and was associated with upregulated tumor necrosis factor and metalloproteinases. After a lag phase, established inflammation was temporospatially associated with destruction of IVDs, cartilage and bone. At later time points, advanced disease was characterised by substantially reduced inflammation, excessive tissue formation and ectopic chondrocyte expansion. These distinct features differentiated affected mice into early, intermediate and advanced disease stages. Excessive tissue formation was observed in vertebral joints only if the IVD was destroyed as a consequence of the early inflammation. Ectopic excessive tissue was predominantly chondroidal with chondrocyte-like cells embedded within collagen type II- and X-rich matrix. This corresponded with upregulation of mRNA for cartilage markers Col2a1, sox9 and Comp. Osteophytes, though infrequent, were more prevalent in later disease. Conclusions The inflammation-driven IVD destruction was shown to be a prerequisite for axial disease progression to osteoproliferation in the PGISp mouse. Osteoproliferation led to vertebral body deformity and fusion but was never seen concurrent with persistent inflammation, suggesting a sequential process. The findings support that early intervention with anti-inflammatory therapies will be needed to limit destructive processes and consequently prevent progression of AS.

Observation of a mixed antiparallel and parallel beta-sheet motif in the crystal structure of Boc-Ala-Ile-Aib-OMe

A diastereomeric mixture of the tripeptide Boc-Ala-Ile-Aib-OMe crystallized in the space group P1 from CH3OH/H2O. The unit cell parameters are a = 10.593(2) A, b = 14.377(3) A, c = 17.872(4) A, alpha = 104.41(2) degrees, beta = 90.55(2) degrees, gamma = 106.91(2) degrees, V = 2512.4 A3, Z = 4. X-Ray crystallographic studies show the presence of four molecules in the asymmetric unit consisting of two pairs of diastereomeric peptides, Boc-L-Ala-L-Ile-Aib-OMe and Boc-L-Ala-D-Ile-Aib-OMe. The four molecules in the asymmetric unit form a rarely found mixed antiparallel and parallel beta-sheet hydrogen bond motif. The Ala and (L,D)-Ile residues in all the four molecules adopt the extended conformations, while the phi, psi values of the Aib residues are in the right-handed helical region. In one of the molecules the Ile sidechain adopts the unusual gauche conformation about the C beta-C gamma bond.

Commodity taxation and parallel imports

We examine the interaction between commodity taxes and parallel imports in a two-country model with imperfect competition. While governments determine non-cooperatively their commodity tax rate, the volume of parallel imports is determined endogenously by the retailing sector. We compare the positive and normative implications of having commodity taxes based on destination or origin principle. We show that, as the volume of parallel imports increases, non-cooperative origin taxes converge, while destination taxes diverge. Moreover, origin taxes are more similar and lead to higher aggregate welfare levels than destination taxes.

Grids with multiple batch systems for performance enhancement of multi-component and parameter sweep parallel applications

In this work, we evaluate the benefits of using Grids with multiple batch systems to improve the performance of multi-component and parameter sweep parallel applications by reduction in queue waiting times. Using different job traces of different loads, job distributions and queue waiting times corresponding to three different queuing policies(FCFS, conservative and EASY backfilling), we conducted a large number of experiments using simulators of two important classes of applications. The first simulator models Community Climate System Model (CCSM), a prominent multi-component application and the second simulator models parameter sweep applications. We compare the performance of the applications when executed on multiple batch systems and on a single batch system for different system and application configurations. We show that there are a large number of configurations for which application execution using multiple batch systems can give improved performance over execution on a single system.

A strategy for scheduling tightly coupled parallel applications on clusters

Although various strategies have been developed for scheduling parallel applications with independent tasks, very little work exists for scheduling tightly coupled parallel applications on cluster environments. In this paper, we compare four different strategies based on performance models of tightly coupled parallel applications for scheduling the applications on clusters. In addition to algorithms based on existing popular optimization techniques, we also propose a new algorithm called Box Elimination that searches the space of performance model parameters to determine the best schedule of machines. By means of real and simulation experiments, we evaluated the algorithms on single cluster and multi-cluster setups. We show that our Box Elimination algorithm generates up to 80% more efficient schedule than other algorithms. We also show that the execution times of the schedules produced by our algorithm are more robust against the performance modeling errors.

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

DMT of Multi-hop Cooperative Networks-Part I: K-Parallel-Path Networks

We consider single-source, single-sink multi-hop relay networks, with slow-fading Rayleigh fading links and single-antenna relay nodes operating under the half-duplex constraint. While two hop relay networks have been studied in great detail in terms of the diversity-multiplexing tradeoff (DMT), few results are available for more general networks. In this two-part paper, we identify two families of networks that are multi-hop generalizations of the two hop network: K-Parallel-Path (KPP) networks and Layered networks. In the first part, we initially consider KPP networks, which can be viewed as the union of K node-disjoint parallel paths, each of length > 1. The results are then generalized to KPP(I) networks, which permit interference between paths and to KPP(D) networks, which possess a direct link from source to sink. We characterize the optimal DMT of KPP(D) networks with K >= 4, and KPP(I) networks with K >= 3. Along the way, we derive lower bounds for the DMT of triangular channel matrices, which are useful in DMT computation of various protocols. As a special case, the DMT of two-hop relay network without direct link is obtained. Two key implications of the results in the two-part paper are that the half-duplex constraint does not necessarily entail rate loss by a factor of two, as previously believed and that, simple AF protocols are often sufficient to attain the best possible DMT.