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.

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.

Application of ultra high performance concrete (UHPC) as a thin-bonded overlay for concrete bridge decks

As transportation infrastructure across the globe approaches the end of its service life, new innovative materials and applications are needed to sustainably repair and prevent damage to these structures. Bridge structures in the United States in particular are at risk as a large percentage will be reaching their design service lives in the coming decades. Superstructure deterioration occurs due to a variety of factors, but a major contributor comes in the form of deteriorating concrete bridge decks. Within a concrete bridge deck system, deterioration mechanisms can include spalling, delaminations, scaling from unsuitable material selection, freeze-thaw damage, and corrosion of reinforcing steel due to infiltration of chloride ions and moisture. This thesis presents findings pertaining to the feasibility of using UHPC as a thin-bonded overlay on concrete bridge decks, specifically in precast bridge deck applications where construction duration and traffic interruption can be minimized, as well as in cast-in-place field applications. UHPC has several properties that make it a desirable material for this application. These properties include post-cracking tensile capacity, high compressive strength, high resistance to environmental and chemical attack, negligible permeability, negligible dry shrinkage when thermally cured, and the ability to self consolidate. The compatibility of this bridge deck overlay system was determined to minimize overlay thickness and dead load without sacrificing bond integrity or lose of protective capabilities. A parametric analysis was conducted using a 3D finite element model of a simply supported bridge under HS-20 truck and overload. Experimental tests were conducted to determine the net effect of UHPC volume change due to restrained shrinkage and tensile creep relaxation. The combined effects from numerical models and test results were then considered in determining the optimum overlay thickness for cast-in-place and precast applications.

Effect of implementing project-based education in high school physics : file folder bridge engineering

Project-based education and portfolio assessments are at the forefront of educational research. This research follows the implementation of a project-based unit in a high school physics class. Students played the role of an engineering firm who designed, built and tested file folder bridges. The purpose was to determine if projectbased learning could improve student attitude toward science and related careers like engineering. Teams of students presented their work in a portfolio for a final assessment of the process of designing, building and testing their bridges.

Evaluation of surface defect detection in reinforced concrete bridge decks using terrestrial LiDAR

Routine bridge inspections require labor intensive and highly subjective visual interpretation to determine bridge deck surface condition. Light Detection and Ranging (LiDAR) a relatively new class of survey instrument has become a popular and increasingly used technology for providing as-built and inventory data in civil applications. While an increasing number of private and governmental agencies possess terrestrial and mobile LiDAR systems, an understanding of the technology’s capabilities and potential applications continues to evolve. LiDAR is a line-of-sight instrument and as such, care must be taken when establishing scan locations and resolution to allow the capture of data at an adequate resolution for defining features that contribute to the analysis of bridge deck surface condition. Information such as the location, area, and volume of spalling on deck surfaces, undersides, and support columns can be derived from properly collected LiDAR point clouds. The LiDAR point clouds contain information that can provide quantitative surface condition information, resulting in more accurate structural health monitoring. LiDAR scans were collected at three study bridges, each of which displayed a varying degree of degradation. A variety of commercially available analysis tools and an independently developed algorithm written in ArcGIS Python (ArcPy) were used to locate and quantify surface defects such as location, volume, and area of spalls. The results were visual and numerically displayed in a user-friendly web-based decision support tool integrating prior bridge condition metrics for comparison. LiDAR data processing procedures along with strengths and limitations of point clouds for defining features useful for assessing bridge deck condition are discussed. Point cloud density and incidence angle are two attributes that must be managed carefully to ensure data collected are of high quality and useful for bridge condition evaluation. When collected properly to ensure effective evaluation of bridge surface condition, LiDAR data can be analyzed to provide a useful data set from which to derive bridge deck condition information.

Determining bridge deck deterioration through the use of 3D photogrammetry

The bridge inspection industry has yet to utilize a rapidly growing technology that shows promise to help improve the inspection process. This thesis investigates the abilities that 3D photogrammetry is capable of providing to the bridge inspector for a number of deterioration mechanisms. The technology can provide information about the surface condition of some bridge components, primarily focusing on the surface defects of a concrete bridge which include cracking, spalling and scaling. Testing was completed using a Canon EOS 7D camera which then processed photos using AgiSoft PhotoScan to align the photos and develop models. Further processing of the models was done using ArcMap in the ArcGIS 10 program to view the digital elevation models of the concrete surface. Several experiments were completed to determine the ability of the technique for the detection of the different defects. The cracks that were able to be resolved in this study were a 1/8 inch crack at a distance of two feet above the surface. 3D photogrammetry was able to be detect a depression of 1 inch wide with 3/16 inch depth which would be sufficient to measure any scaling or spalling that would be required be the inspector. The percentage scaled or spalled was also able to be calculated from the digital elevation models in ArcMap. Different camera factors including the distance from the defects, number of photos and angle, were also investigated to see how each factor affected the capabilities. 3D photogrammetry showed great promise in the detection of scaling or spalling of the concrete bridge surface.

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.

Infrared Thermography Enhancements for Concrete Bridge Evaluation

Infrared thermography is a well-recognized non-destructive testing technique for evaluating concrete bridge elements such as bridge decks and piers. However, overcoming some obstacles and limitations are necessary to be able to add this invaluable technique to the bridge inspector's tool box. Infrared thermography is based on collecting radiant temperature and presenting the results as a thermal infrared image. Two methods considered in conducting an infrared thermography test include passive and active. The source of heat is the main difference between these two approaches of infrared thermography testing. Solar energy and ambient temperature change are the main heat sources in conducting a passive infrared thermography test, while active infrared thermography involves generating a temperature gradient using an external source of heat other than sun. Passive infrared thermography testing was conducted on three concrete bridge decks in Michigan. Ground truth information was gathered through coring several locations on each bridge deck to validate the results obtained from the passive infrared thermography test. Challenges associated with data collection and processing using passive infrared thermography are discussed and provide additional evidence to confirm that passive infrared thermography is a promising remote sensing tool for bridge inspections. To improve the capabilities of the infrared thermography technique for evaluation of the underside of bridge decks and bridge girders, an active infrared thermography technique using the surface heating method was developed in the laboratory on five concrete slabs with simulated delaminations. Results from this study demonstrated that active infrared thermography not only eliminates some limitations associated with passive infrared thermography, but also provides information regarding the depth of the delaminations. Active infrared thermography was conducted on a segment of an out-of-service prestressed box beam and cores were extracted from several locations on the beam to validate the results. This study confirms the feasibility of the application of active infrared thermography on concrete bridges and of estimating the size and depth of delaminations. From the results gathered in this dissertation, it was established that applying both passive and active thermography can provide transportation agencies with qualitative and quantitative measures for efficient maintenance and repair decision-making.

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.