Analysis and performance of a UPC implementation of a parallel longest common subsequence algorithm

An important problem in computational biology is finding the longest common subsequence (LCS) of two nucleotide sequences. This paper examines the correctness and performance of a recently proposed parallel LCS algorithm that uses successor tables and pruning rules to construct a list of sets from which an LCS can be easily reconstructed. Counterexamples are given for two pruning rules that were given with the original algorithm. Because of these errors, performance measurements originally reported cannot be validated. The work presented here shows that speedup can be reliably achieved by an implementation in Unified Parallel C that runs on an Infiniband cluster. This performance is partly facilitated by exploiting the software cache of the MuPC runtime system. In addition, this implementation achieved speedup without bulk memory copy operations and the associated programming complexity of message passing.

Advanced mechanics of materials with microstructure

The study of advanced materials aimed at improving human life has been performed since time immemorial. Such studies have created everlasting and greatly revered monuments and have helped revolutionize transportation by ushering the age of lighter–than–air flying machines. Hence a study of the mechanical behavior of advanced materials can pave way for their use for mankind’s benefit. In this school of thought, the aim of this dissertation is to broadly perform two investigations. First, an efficient modeling approach is established to predict the elastic response of cellular materials with distributions of cell geometries. Cellular materials find important applications in structural engineering. The approach does not require complex and time-consuming computational techniques usually associated with modeling such materials. Unlike most current analytical techniques, the modeling approach directly accounts for the cellular material microstructure. The approach combines micropolar elasticity theory and elastic mixture theory to predict the elastic response of cellular materials. The modeling approach is applied to the two dimensional balsa wood material. Predicted properties are in good agreement with experimentally determined properties, which emphasizes the model’s potential to predict the elastic response of other cellular solids, such as open cell and closed cell foams. The second topic concerns intraneural ganglion cysts which are a set of medical conditions that result in denervation of the muscles innervated by the cystic nerve leading to pain and loss of function. Current treatment approaches only temporarily alleviate pain and denervation which, however, does not prevent cyst recurrence. Hence, a mechanistic understanding of the pathogenesis of intraneural ganglion cysts can help clinicians understand them better and therefore devise more effective treatment options. In this study, an analysis methodology using finite element analysis is established to investigate the pathogenesis of intraneural ganglion cysts. Using this methodology, the propagation of these cysts is analyzed in their most common site of occurrence in the human body i.e. the common peroneal nerve. Results obtained using finite element analysis show good correlation with clinical imaging patterns thereby validating the promise of the method to study cyst pathogenesis.

Parallel algorithm for solving integer linear programs

Linear programs, or LPs, are often used in optimization problems, such as improving manufacturing efficiency of maximizing the yield from limited resources. The most common method for solving LPs is the Simplex Method, which will yield a solution, if one exists, but over the real numbers. From a purely numerical standpoint, it will be an optimal solution, but quite often we desire an optimal integer solution. A linear program in which the variables are also constrained to be integers is called an integer linear program or ILP. It is the focus of this report to present a parallel algorithm for solving ILPs. We discuss a serial algorithm using a breadth-first branch-and-bound search to check the feasible solution space, and then extend it into a parallel algorithm using a client-server model. In the parallel mode, the search may not be truly breadth-first, depending on the solution time for each node in the solution tree. Our search takes advantage of pruning, often resulting in super-linear improvements in solution time. Finally, we present results from sample ILPs, describe a few modifications to enhance the algorithm and improve solution time, and offer suggestions for future work.

Development of a continuum mechanics model of passive skeletal muscle

Skeletal muscle force evaluation is difficult to implement in a clinical setting. Muscle force is typically assessed through either manual muscle testing, isokinetic/isometric dynamometry, or electromyography (EMG). Manual muscle testing is a subjective evaluation of a patient’s ability to move voluntarily against gravity and to resist force applied by an examiner. Muscle testing using dynamometers adds accuracy by quantifying functional mechanical output of a limb. However, like manual muscle testing, dynamometry only provides estimates of the joint moment. EMG quantifies neuromuscular activation signals of individual muscles, and is used to infer muscle function. Despite the abundance of work performed to determine the degree to which EMG signals and muscle forces are related, the basic problem remains that EMG cannot provide a quantitative measurement of muscle force. Intramuscular pressure (IMP), the pressure applied by muscle fibers on interstitial fluid, has been considered as a correlate for muscle force. Numerous studies have shown that an approximately linear relationship exists between IMP and muscle force. A microsensor has recently been developed that is accurate, biocompatible, and appropriately sized for clinical use. While muscle force and pressure have been shown to be correlates, IMP has been shown to be non-uniform within the muscle. As it would not be practicable to experimentally evaluate how IMP is distributed, computational modeling may provide the means to fully evaluate IMP generation in muscles of various shapes and operating conditions. The work presented in this dissertation focuses on the development and validation of computational models of passive skeletal muscle and the evaluation of their performance for prediction of IMP. A transversly isotropic, hyperelastic, and nearly incompressible model will be evaluated along with a poroelastic model.

Development of a high performance parallel computing platform and its use in the study of nanostructures : clusters, sheets and tubes .

Small clusters of gallium oxide, technologically important high temperature ceramic, together with interaction of nucleic acid bases with graphene and small-diameter carbon nanotube are focus of first principles calculations in this work. A high performance parallel computing platform is also developed to perform these calculations at Michigan Tech. First principles calculations are based on density functional theory employing either local density or gradient-corrected approximation together with plane wave and gaussian basis sets. The bulk Ga2O3 is known to be a very good candidate for fabricating electronic devices that operate at high temperatures. To explore the properties of Ga2O3 at nonoscale, we have performed a systematic theoretical study on the small polyatomic gallium oxide clusters. The calculated results find that all lowest energy isomers of GamOn clusters are dominated by the Ga-O bonds over the metal-metal or the oxygen-oxygen bonds. Analysis of atomic charges suggest the clusters to be highly ionic similar to the case of bulk Ga2O3. In the study of sequential oxidation of these slusters starting from Ga2O, it is found that the most stable isomers display up to four different backbones of constituent atoms. Furthermore, the predicted configuration of the ground state of Ga2O is recently confirmed by the experimental result of Neumark's group. Guided by the results of calculations the study of gallium oxide clusters, performance related challenge of computational simulations, of producing high performance computers/platforms, has been addressed. Several engineering aspects were thoroughly studied during the design, development and implementation of the high performance parallel computing platform, rama, at Michigan Tech. In an attempt to stay true to the principles of Beowulf revolutioni, the rama cluster was extensively customized to make it easy to understand, and use - for administrators as well as end-users. Following the results of benchmark calculations and to keep up with the complexity of systems under study, rama has been expanded to a total of sixty four processors. Interest in the non-covalent intereaction of DNA with carbon nanotubes has steadily increased during past several years. This hybrid system, at the junction of the biological regime and the nanomaterials world, possesses features which make it very attractive for a wide range of applicatioins. Using the in-house computational power available, we have studied details of the interaction between nucleic acid bases with graphene sheet as well as high-curvature small-diameter carbon nanotube. The calculated trend in the binding energies strongly suggests that the polarizability of the base molecules determines the interaction strength of the nucleic acid bases with graphene. When comparing the results obtained here for physisorption on the small diameter nanotube considered with those from the study on graphene, it is observed that the interaction strength of nucleic acid bases is smaller for the tube. Thus, these results show that the effect of introducing curvature is to reduce the binding energy. The binding energies for the two extreme cases of negligible curvature (i.e. flat graphene sheet) and of very high curvature (i.e. small diameter nanotube) may be considered as upper and lower bounds. This finding represents an important step towards a better understanding of experimentally observed sequence-dependent interaction of DNA with Carbon nanotubes.

PARTITIONING THE BLOCKS OF A STEINER TRIPLE SYSTEM INTO PARTIAL PARALLEL CLASSES

Does there exist a Steiner Triple System on v points, whose blocks can be partitioned into partial parallel classes of size m, where m ≤ [v⁄3], m | b and b is the number of blocks of the STS(v)? We give the answer for 9 ≤ v ≤ 43. We also show that whenever 2|b, v ≡ 3 (mod 6) we can find an STS(v) whose blocks can be partitioned into partial parallel classes of size 2, and whenever 4|b , v ≡ 3 (mod 6), there exists an STS(v) whose blocks can be partitioned into partial parallel classes of size 4.