My research has been on the development of concurrent algorithms for shared memory systems that provide guarantees of progress. Research into such algorithms is important to developers implementing applications on mission critical and time sensitive systems. These guarantees of progress provide safety properties and freedom from many hazards, such as dead-lock, live-lock, and thread starvation. In addition to the safety concerns, the fine-grained synchronization used in implementing these algorithms promises to provide scalable performance in massively parallel systems. My research has resulted in the development of wait-free versions of the stack, hash map, ring buffer, vector, and a multi-word compare-and-swap algorithms. Through this experience, I have learned and developed new techniques and methodologies for implementing non-blocking and wait-free algorithms. I have worked with and refined existing techniques to improve their practicality and applicability. In the creation of the aforementioned algorithms, I have developed an association model for use with descriptor-based operations. This model, originally developed for the multi-word compare-and-swap algorithm, has been applied to the design of the vector and ring buffer algorithms. To unify these algorithms and techniques, I have released Tervel, a wait-free library of common algorithms and containers. This library includes a framework that simplifies and improves the design of non-blocking algorithms. I have reimplemented several algorithms using this framework and the resulting implementation exhibits less code duplication and fewer perceivable states. When reimplementing algorithms, I have adapted their Application Programming Interface (API) specification to remove ambiguity and non-deterministic behavior found when using a sequential API in a concurrent environment. To improve the performance of my algorithm implementations, I extended OVIS's Lightweight Distributed Metric Service (LDMS)'s data collection and transport system to support performance monitoring using perf_event and PAPI libraries. These libraries have provided me with deeper insights into the behavior of my algorithms, and I was able to use these insights to improve the design and performance of my algorithms.

No description available.

No description available.

No description available.

This research addresses decisions involved in the design of an order picking system in a distribution center. A distribution center (DC) in a logistics system is responsible for obtaining materials from different suppliers and assembling (or sorting) them to fulfill a number of different customer orders. Order picking, which is a key activity in a DC, refers to the operation through which items are retrieved from storage locations to fulfill customer orders. Several decisions are involved when designing an order picking system (OPS). Some of these decisions include the identification of the picking-area layout, configuration of the storage system, and determination of the storage policy, picking method, picking strategy, material handling system, pick-assist technology, etc. For a given set of these parameters, the best design depends on the objective function (e.g., maximizing throughout, minimizing cost, etc.) being optimized. The overall goal of this research is to develop a set of analytical models for OPS design. The idea is to help an OPS designer to identify the best performing alternatives out of a large number of possible alternatives. Such models will complement experienced-based or simulation-based approaches, with the goal of improving the efficiency and efficacy of the design process. In this dissertation we focus on the following two key OPS design issues: configuration of the storage system and selection between batch and zone order picking strategies. Several factors that affect these decisions are identified in this dissertation; a common factor amongst these being picker blocking. We first develop models to estimate picker blocking (Contribution 1) and use the picker blocking estimates in addressing the two OPS design issues, presented as Contributions 2 and 3. In Contribution 1 we develop analytical models using discrete-time Markov chains to estimate pick-face blocking in wide-aisle OPSs. Pick-face blocking refers to the blocking experienced by a picker at a pick-face when another picker is already picking at that pick-face. We observe that for the case when pickers may pick only one item at a pick-face, similar to in-the-aisle blocking, pick-face blocking first increases with an increase in pick-density and then decreases. Moreover, pick-face blocking increases with an increase in the number of pickers and pick to walk time ratio, while it decreases with an increase in the number of pick-faces. For the case when pickers may pick multiple items at a pick-face, pick-face blocking increases monotonically with an increase in the pick-density. These blocking estimates are used in addressing the two OPS design issues, which are presented as Contributions 2 and 3. In Contribution 2 we address the issue of configuring the storage system for order picking. A storage system, typically comprised of racks, is used to store pallet-loads of various stock keeping units (SKU) --- a SKU is a unique identifier of products or items that are stored in a DC. The design question we address is related to identifying the optimal height (i.e., number of storage levels), and thus length, of a one-pallet-deep storage system. We develop a cost-based optimization model in which the number of storage levels is the decision variable and satisfying system throughput is the constraint. The objective of the model is to minimize the system cost, which is comprised of the cost of labor and space. To estimate the cost of labor we first develop a travel-time model for a person-aboard storage/retrieval (S/R) machine performing Tchebyshev travel as it travels in the aisle. Then, using this travel-time model we estimate the throughput of each picker, which helps us estimate the number of pickers required to satisfy the system throughput for a given number of storage levels. An estimation of the cost of space is also modeled to complete the total cost model. Results from an experimental study suggest that a low (in height) and long (in length) storage system tends to be optimal for situations where there is a relatively low number of storage locations and a relatively high throughput requirement; this is in contrast with common industry perception of the higher the better. The primary reason for this contrast is because the industry does not consider picker blocking and vertical travel of the S/R machine. On the other hand, results from the same optimization model suggest that a manual OPS should, in almost all situations, employ a high (in height) and short (in length) storage system; a result that is consistent with industry practice. This consistency is expected as picker blocking and vertical travel, ignored in industry, are not a factor in a manual OPS. In Contribution 3 we address the issue of selecting between batch and zone picking strategies. A picking strategy defines the manner in which the pickers navigate the picking aisles of a storage area to pick the required items. Our aim is to help the designer in identifying the least expensive picking strategy to be employed that meets the system throughput requirements. Consequently, we develop a cost model to estimate the system cost of a picking system that employs either a batch or a zone picking strategy. System cost includes the cost of pickers, equipment, imbalance, sorting system, and packers. Although all elements are modeled, we highlight the development of models to estimate the cost of imbalance and sorting system. Imbalance cost refers to the cost of fulfilling the left-over items (in customer orders) due to workload-imbalance amongst pickers. To estimate the imbalance cost we develop order batching models, the solving of which helps in identifying the number of items unfulfilled. We also develop a comprehensive cost model to estimate the cost of an automated sorting system. To demonstrate the use of our models we present an illustrative example that compares a sort-while-pick batch picking system with a simultaneous zone picking system. To summarize, the overall goal of our research is to develop a set of analytical models to help the designer in designing order picking systems in a distribution center. In this research we focused on two key design issues and addressed them through analytical approaches. Our future research will focus on addressing other design issues and incorporating them in a decision support system. / Ph. D.

The turbulent flow through a marine propulsor was experimentally modeled using a large cascade configuration with six 33 cm chord flat plates spanning the entire height of the test section in the Virginia Tech Stability Wind Tunnel. Three-component hot-wire velocity measurements were obtained ahead, throughout and behind both an unstaggered and a 35º staggered cascade configuration with blade spacing and onset turbulence integral scales on the order of the chord. This provided a much needed data-set of much larger Taylor Reynolds number than previous related studies and allowed a thorough investigation of the blade-blocking effects of the cascade on the incident turbulent field. In order to generate the large scale turbulence needed for this study, a mechanically rotating "active" grid design was adopted and placed in the contraction of the wind tunnel at a streamwise location sufficient to cancel out the relatively large inherent low frequency anisotropy associated with this type of grid. The resulting turbulent flow is one of the largest Reynolds number (Reλ  1000) homogeneous near-isotropic turbulent flows ever created in a wind tunnel, and provided the opportunity to investigate Reynolds number effects on turbulence parameters, especially relating to inertial range dynamics. Key findings include 1) that the extent of local isotropy is solely determined by the turbulence generator and the size of the wind-tunnel that houses it; and 2) that the turbulence generator operating conditions affect the shape of the equilibrium range at fixed Taylor Reynolds number. The latter finding suggests that grid turbulence is not necessarily self-similar at a given Reynolds number independent of how it was generated. The experimental blade-blocking data was compared to linear cascade theory and showed good qualitative agreement, especially for wavenumbers above the region of influence of the wind tunnel and turbulence generator effects. As predicted, the turbulence is permanently modified by the presence of the cascade after which it remains invariant for a significant downstream distance outside the thin viscous regions. The obtained results support the claim that Rapid Distortion Theory (RDT) is capable of providing reasonable estimates of the flow behind the cascade even though the experimental conditions lie far outside the predicted region of validity. / Ph. D.

The mechanisms by which antipsychotics (neuroleptics) produce their therapeutic effects in schizophrenia are largely unknown. Although neuroleptic efficacy is attributed to central dopamine D2 and/or serotonin 5-HT2 receptor antagonism, clinical improvements in schizophrenia are not seen until two or three weeks after daily neuroleptic administration. The mechanisms underlying the neuroleptic response must therefore occur downstream from initial receptor blockade and be a consequence of chronic neurotransmitter receptor blockade. The goal of the present study was to use neuroleptics with varied dopamine vs. serotonergic receptor blocking profiles to elucidate some of these intracellular post receptor mechanisms. Since the final steps of both dopamine and serotonin synthesis require the enzyme aromatic L-amino acid decarboxylase (AADC), the effects of neuroleptics on AADC gene (mRNA) expression were examined in PC12 cells and compared to their effects on the synthetic enzyme tyrosine hydroxylase (TH) and ' c-fos' (an early immediate gene [IEG]) mRNA. The neuroleptics examined did not significantly regulate AADC mRNA in PC12 cells, and only haloperidol upregulated TH and 'c-fos' mRNA. Later studies in rats showed that acute neuroleptic administration increased ' c-fos' mRNA, whereas the immunoreactivity of a related IEG (delta FosB) was increased upon chronic treatment. These studies and a subsequent dose response study demonstrated that upregulation of both 'c-fos' mRNA and delta FosB immunoreactivity was most prominent in dopaminergic projection areas including the striatum and nucleus accumbens. Because it has been suggested that neuroleptic treatment might prevent neurodegeneration in schizophrenia, the effects of neuroleptics on the mRNA expression of neuroprotective target genes of delta FosB were examined both ' in vivo' and 'in vitro'. These genes included brain-derived neurotrophic factor (BDNF), the neuroprotective enzyme superoxide dismutase (SOD), and the low affinity nerve growth factor receptor (p75). While dopamine D2 blockade unfavorably regulated BDNF and p75 mRNA, 5-HT 2 blockade either had no effect on or favorably regulated BDNF, SOD, and p75 mRNA. Thus, although little about the contribution of serotonergic blockade in the neuroleptic response was determined, dopaminergic blockade regulated IEG's and several of their target genes. Future studies will be needed to understand the role of 5-HT2 receptor blockade in the neuroleptic response.

V této práci představujeme blokovou metodu pro zlepšení lokality v cache paměti u výpočtů typu stencil a dva nástroje, Pluto a PATUS, které tuto metodu používají ke generování optimalizovaného kódu. Provádíme různá měření a zkoumáme zrychlení výpočtu při použití různých optimalizací. Nakonec implementujeme vyhlazovací krok v multigridu s různými optimalizacemi a zkoumáme jak se tyto optimalizace projeví na výkonu multigridu.

A CONWIP (Constant Work-In-Progress) system is basically a hybrid system with a PUSH-PULL interface at the first machine in the line. This research addresses the most general case of a cyclic CONWIP system by incorporating two additional constraints over earlier studies namely; stochastic processing times and limited intermediate storage. One of the main issues in the design of a CONWIP system is the WIP level 'M', to be maintained. This research proposes an iterative procedure to determine this optimal level. The second main issue is the optimization of the line by determining an appropriate job sequence. This research assumes a 'permutational' scheduling policy and proposes an iterative approach to find the best sequence. The approach utilizes a controlled enumerative approach called the Fast Insertion Heuristic (FIH) coupled with a method to appraise the quality of every enumeration at each iteration. This is done by using a modified version of the Floyd's algorithm, to determine the cycle time (or Flow time) of a partial/full solution. The performance measures considered are the Flow time and the Interdeparture time (inverse of throughput). Finally, both the methods suggested for the two subproblems, are tested through computer implementations to reveal their proficiency. / Master of Science

In this report we describe the conversion of a simple Master-Worker parallel program from global blocking communications to non-blocking communications. The program is MPI-based and has been run on different computer architectures. By moving the communication to the background the processors can use the former waiting time for computation. However we find that the computing time increases by the time the communication time decreases in the used MPICH implementation on a cluster of workstations. Also using non-global communication instead of the global communication slows the algorithm down on computers with optimized global communication routines like the Cray T3D.