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.

Control design and genetic algorithm optimization for electrostatic MEMS

This dissertation discusses structural-electrostatic modeling techniques, genetic algorithm based optimization and control design for electrostatic micro devices. First, an alternative modeling technique, the interpolated force model, for electrostatic micro devices is discussed. The method provides improved computational efficiency relative to a benchmark model, as well as improved accuracy for irregular electrode configurations relative to a common approximate model, the parallel plate approximation model. For the configuration most similar to two parallel plates, expected to be the best case scenario for the approximate model, both the parallel plate approximation model and the interpolated force model maintained less than 2.2% error in static deflection compared to the benchmark model. For the configuration expected to be the worst case scenario for the parallel plate approximation model, the interpolated force model maintained less than 2.9% error in static deflection while the parallel plate approximation model is incapable of handling the configuration. Second, genetic algorithm based optimization is shown to improve the design of an electrostatic micro sensor. The design space is enlarged from published design spaces to include the configuration of both sensing and actuation electrodes, material distribution, actuation voltage and other geometric dimensions. For a small population, the design was improved by approximately a factor of 6 over 15 generations to a fitness value of 3.2 fF. For a larger population seeded with the best configurations of the previous optimization, the design was improved by another 7% in 5 generations to a fitness value of 3.0 fF. Third, a learning control algorithm is presented that reduces the closing time of a radiofrequency microelectromechanical systems switch by minimizing bounce while maintaining robustness to fabrication variability. Electrostatic actuation of the plate causes pull-in with high impact velocities, which are difficult to control due to parameter variations from part to part. A single degree-of-freedom model was utilized to design a learning control algorithm that shapes the actuation voltage based on the open/closed state of the switch. Experiments on 3 test switches show that after 5-10 iterations, the learning algorithm lands the switch with an impact velocity not exceeding 0.2 m/s, eliminating bounce.

Spatial and temporal analysis of land cover and landscape structure change in Zagros Forests

The Zagros oak forests in Western Iran are critically important to the sustainability of the region. These forests have undergone dramatic declines in recent decades. We evaluated the utility of the non-parametric Random Forest classification algorithm for land cover classification of Zagros landscapes, and selected the best spatial and spectral predictive variables. The algorithm resulted in high overall classification accuracies (>85%) and also equivalent classification accuracies for the datasets from the three different sensors. We evaluated the associations between trends in forest area and structure with trends in socioeconomic and climatic conditions, to identify the most likely driving forces creating deforestation and landscape structure change. We used available socioeconomic (urban and rural population, and rural income), and climatic (mean annual rainfall and mean annual temperature) data for two provinces in northern Zagros. The most correlated driving force of forest area loss was urban population, and climatic variables to a lesser extent. Landscape structure changes were more closely associated with rural population. We examined the effects of scale changes on the results from spatial pattern analysis. We assessed the impacts of eight years of protection in a protected area in northern Zagros at two different scales (both grain and extent). The effects of protection on the amount and structure of forests was scale dependent. We evaluated the nature and magnitude of changes in forest area and structure over the entire Zagros region from 1972 to 2009. We divided the Zagros region in 167 Landscape Units and developed two measures— Deforestation Sensitivity (DS) and Connectivity Sensitivity (CS) — for each landscape unit as the percent of the time steps that forest area and ECA experienced a decrease of greater than 10% in either measure. A considerable loss in forest area and connectivity was detected, but no sudden (nonlinear) changes were detected at the spatial and temporal scale of the study. Connectivity loss occurred more rapidly than forest loss due to the loss of connecting patches. More connectivity was lost in southern Zagros due to climatic differences and different forms of traditional land use.

EVALUATION OF MAGNESIUM AS A HALL THRUSTER PROPELLANT

In this study, the use of magnesium as a Hall thruster propellant was evaluated. A xenon Hall thruster was modified such that magnesium propellant could be loaded into the anode and use waste heat from the thruster discharge to drive the propellant vaporization. A control scheme was developed, which allowed for precise control of the mass flow rate while still using plasma heating as the main mechanism for evaporation. The thruster anode, which also served as the propellant reservoir, was designed such that the open area was too low for sufficient vapor flow at normal operating temperatures (i.e. plasma heating alone). The remaining heat needed to achieve enough vapor flow to sustain thruster discharge came from a counter-wound resistive heater located behind the anode. The control system has the ability to arrest thermal runaway in a direct evaporation feed system and stabilize the discharge current during voltage-limited operation. A proportional-integral-derivative control algorithm was implemented to enable automated operation of the mass flow control system using the discharge current as the measured variable and the anode heater current as the controlled parameter. Steady-state operation at constant voltage with discharge current excursions less than 0.35 A was demonstrated for 70 min. Using this long-duration method, stable operation was achieved with heater powers as low as 6% of the total discharge power. Using the thermal mass flow control system the thruster operated stably enough and long enough that performance measurements could be obtained and compared to the performance of the thruster using xenon propellant. It was found that when operated with magnesium, the thruster has thrust ranging from 34 mN at 200 V to 39 mN at 300 V with 1.7 mg/s of propellant. It was found to have 27 mN of thrust at 300 V using 1.0 mg/s of propellant. The thrust-to-power ratio ranged from 24 mN/kW at 200 V to 18 mN/kW at 300 volts. The specific impulse was 2000 s at 200 V and upwards of 2700 s at 300 V. The anode efficiency was found to be ~23% using magnesium, which is substantially lower than the 40% anode efficiency of xenon at approximately equivalent molar flow rates. Measurements in the plasma plume of the thruster—operated using magnesium and xenon propellants—were obtained using a Faraday probe to measure off-axis current distribution, a retarding potential analyzer to measure ion energy, and a double Langmuir probe to measure plasma density, electron temperature, and plasma potential. Additionally, the off axis current distributions and ion energy distributions were compared to measurements made in krypton and bismuth plasmas obtained in previous studies of the same thruster. Comparisons showed that magnesium had the largest beam divergence of the four propellants while the others had similar divergence. The comparisons also showed that magnesium and krypton both had very low voltage utilization compared to xenon and bismuth. It is likely that the differences in plume structure are due to the atomic differences between the propellants; the ionization mean free path goes down with increasing atomic mass. Magnesium and krypton have long ionization mean free paths and therefore require physically larger thruster dimensions for efficient thruster operation and would benefit from magnetic shielding.