Narrow Results

A variety of algorithms have been proposed for sparse Cholesky factorization, including left-looking, right-looking, and supernodal algorithms. This article investigates shared-memory implementations of several variants of these algorithms in a task-oriented execution model with dynamic scheduling. In particular, we consider the degree of parallelism, the scalability, and the scheduling overhead of the different algorithms. Our emphasis lies in the parallel implementation for relatively large numbers of processors. As execution platform, we use the SB-PRAM, a shared-memory machine with up to 2048 processors. This article can be considered as a case study in which we try to answer the question of which performance we can hope to get for a typical irregular application on an ideal machine on which the locality of memory accesses can be ignored but for which the overhead for the management of data structures still takes effect. The investigation shows that certain algorithms are the best choice for a small number of processors, while other algorithms are better for many processors.

We examine multiprocessor runtime support for fine-grained, irregular directed acyclic graphs (DAGs) such as those that arise from sparse-matrix triangular solves. We conduct our experiments on the CM-5, whose lower latencies and active-message support allow us to achieve unprecedented speedups for a general multiprocessor. Where as previous implementations have maximum speedups of less than 4 on even simple banded matrices, we are able to obtain scalable performance on extremely small and irregular problems. On a matrix with only 5300 rows, we are able to achieve scalable performance with a speedup of 34 for 128 processors, resulting in an absolute performance of over 33 million double-precision floating point operations per second.

We achieve these speedups with non-matrix-specific methods which are applicable to any DAG. We compare a range of run-time preprocessed and dynamic approaches on matrices from the Harwell-Boeing benchmark set. Although precomputed data distributions and execution schedules produce the best performance, we find that it is challenging to keep their cost low enough to make them worthwhile on small, fine-grained problems.

Additionally, we find that a policy of frequent network polling can reduce communication overhead by a factor of three over the standard CM-5 policies. We present a detailed study of runtime overheads and demonstrate that send and receive processor overhead still dominate these applications on the CM-5. We conclude that these applications would highly benefit from architectural support for low-overhead communication.

The benefits of hardware support for shared memory versus those for message passing are difficult to evaluate without an in-depth study of real applications on a common platform. We evaluate the communication mechanisms of the MIT Alewife machine, a multiprocessor which provides integrated cache-coherent shared memory, massage passing, and DMA. We perform this evaluation with "best-effort" implementations which solve several sparse, irregular benchmark problems with a preconditioned conjugate gradient sparse matrix solver (ICCG).

We find that machines with fast global memory operations do not need message passing or bulk transfer to suport our irregular problems. This is primarily due to three reasons. First, a 5-to-1 ratio between global and local cache misses makes memory copies in bulk communication expensive relati to communication via shared memory. Second, although message passing has synchronization semantics superior to shared memory for data-driven computation, efficient shared memory can overcome this handicap by using global read-modify-writes to change from the traditional owner-computers model to a producer-computes model. Third, bulk transfers can result in high processor idle times in irregular applications.

Protein secondary structure prediction (PSSP) is an important and challenging task in protein bioinformatics. Protein secondary structures (SSs) are categorized in regular and irregular structure classes. Regular SSs, representing nearly 50% of amino acids consist of helices and sheets, whereas the remaining amino acids represent irregular SSs. $\beta$-turns and $\gamma$-turns are the most abundant irregular SSs present in proteins. Existing methods are well developed for separate prediction of regular and irregular SSs. However, for more comprehensive PSSP, it is essential to develop a uniform model to predict all types of SSs simultaneously. In this work, using a novel dataset comprising dictionary of secondary structure of protein (DSSP)-based SSs and PROMOTIF-based $\beta$-turns and $\gamma$-turns, we propose a unified deep learning model consisting of convolutional neural networks (CNNs) and long short-term memory networks (LSTMs) for simultaneous prediction of regular and irregular SSs. To the best of our knowledge, this is the first study in PSSP covering both regular and irregular structures. The protein sequences in our constructed datasets, RiR6069 and RiR513, have been borrowed from benchmark CB6133 and CB513 datasets, respectively. The results are indicative of increased PSSP accuracy.

Buildings on hill slope are highly irregular and asymmetric in plan and elevation. They are subjected to severe torsion in addition to lateral forces under the action of earthquakes. In the present study, simplified 3D dynamic analysis of hill buildings based on transformation of stiffness and mass of various components about a common arbitrarily-chosen reference axis is presented. Few actual hill building problems have been analysed with the simplifed method and the rigorous method of analysis. The results of the two methods of analysis advocate the use of the simplified method in the Code of Practices of different countries. With the use of the simplified method, the configurations for buildings on hill slope can be decided by taking various trial configurations so as to obtain the most economical and safe design from the seismic point of view.