Thread Scheduling Mechanisms for Multiple-Context Parallel Processors

Scheduling tasks to efficiently use the available processor resources is crucial to minimizing the runtime of applications on shared-memory parallel processors. One factor that contributes to poor processor utilization is the idle time caused by long latency operations, such as remote memory references or processor synchronization operations. One way of tolerating this latency is to use a processor with multiple hardware contexts that can rapidly switch to executing another thread of computation whenever a long latency operation occurs, thus increasing processor utilization by overlapping computation with communication. Although multiple contexts are effective for tolerating latency, this effectiveness can be limited by memory and network bandwidth, by cache interference effects among the multiple contexts, and by critical tasks sharing processor resources with less critical tasks. This thesis presents techniques that increase the effectiveness of multiple contexts by intelligently scheduling threads to make more efficient use of processor pipeline, bandwidth, and cache resources. This thesis proposes thread prioritization as a fundamental mechanism for directing the thread schedule on a multiple-context processor. A priority is assigned to each thread either statically or dynamically and is used by the thread scheduler to decide which threads to load in the contexts, and to decide which context to switch to on a context switch. We develop a multiple-context model that integrates both cache and network effects, and shows how thread prioritization can both maintain high processor utilization, and limit increases in critical path runtime caused by multithreading. The model also shows that in order to be effective in bandwidth limited applications, thread prioritization must be extended to prioritize memory requests. We show how simple hardware can prioritize the running of threads in the multiple contexts, and the issuing of requests to both the local memory and the network. Simulation experiments show how thread prioritization is used in a variety of applications. Thread prioritization can improve the performance of synchronization primitives by minimizing the number of processor cycles wasted in spinning and devoting more cycles to critical threads. Thread prioritization can be used in combination with other techniques to improve cache performance and minimize cache interference between different working sets in the cache. For applications that are critical path limited, thread prioritization can improve performance by allowing processor resources to be devoted preferentially to critical threads. These experimental results show that thread prioritization is a mechanism that can be used to implement a wide range of scheduling policies.

Parallel Coupled Micro-Macro Actuators

This thesis presents a new actuator system consisting of a micro-actuator and a macro-actuator coupled in parallel via a compliant transmission. The system is called the Parallel Coupled Micro-Macro Actuator, or PaCMMA. In this system, the micro-actuator is capable of high bandwidth force control due to its low mass and direct-drive connection to the output shaft. The compliant transmission of the macro-actuator reduces the impedance (stiffness) at the output shaft and increases the dynamic range of force. Performance improvement over single actuator systems was expected in force control, impedance control, force distortion and reduction of transient impact forces. A set of quantitative measures is proposed and the actuator system is evaluated against them: Force Control Bandwidth, Position Bandwidth, Dynamic Range, Impact Force, Impedance ("Backdriveability'"), Force Distortion and Force Performance Space. Several theoretical performance limits are derived from the saturation limits of the system. A control law is proposed and control system performance is compared to the theoretical limits. A prototype testbed was built using permanenent magnet motors and an experimental comparison was performed between this actuator concept and two single actuator systems. The following performance was observed: Force bandwidth of 56Hz, Torque Dynamic Range of 800:1, Peak Torque of 1040mNm, Minimum Torque of 1.3mNm. Peak Impact Force was reduced by an order of magnitude. Distortion at small amplitudes was reduced substantially. Backdriven impedance was reduced by 2-3 orders of magnitude. This actuator system shows promise for manipulator design as well as psychophysical tests of human performance.

ADAM: A Decentralized Parallel Computer Architecture Featuring Fast Thread and Data Migration and a Uniform Hardware Abstraction

The furious pace of Moore's Law is driving computer architecture into a realm where the the speed of light is the dominant factor in system latencies. The number of clock cycles to span a chip are increasing, while the number of bits that can be accessed within a clock cycle is decreasing. Hence, it is becoming more difficult to hide latency. One alternative solution is to reduce latency by migrating threads and data, but the overhead of existing implementations has previously made migration an unserviceable solution so far. I present an architecture, implementation, and mechanisms that reduces the overhead of migration to the point where migration is a viable supplement to other latency hiding mechanisms, such as multithreading. The architecture is abstract, and presents programmers with a simple, uniform fine-grained multithreaded parallel programming model with implicit memory management. In other words, the spatial nature and implementation details (such as the number of processors) of a parallel machine are entirely hidden from the programmer. Compiler writers are encouraged to devise programming languages for the machine that guide a programmer to express their ideas in terms of objects, since objects exhibit an inherent physical locality of data and code. The machine implementation can then leverage this locality to automatically distribute data and threads across the physical machine by using a set of high performance migration mechanisms. An implementation of this architecture could migrate a null thread in 66 cycles -- over a factor of 1000 improvement over previous work. Performance also scales well; the time required to move a typical thread is only 4 to 5 times that of a null thread. Data migration performance is similar, and scales linearly with data block size. Since the performance of the migration mechanism is on par with that of an L2 cache, the implementation simulated in my work has no data caches and relies instead on multithreading and the migration mechanism to hide and reduce access latencies.

Control of a compliant two-axis robotic arm

In order to ease control, the links between actuators and robotic limbs are generally made to be as stiff as possible. This is in contrast to natural limbs, where compliance is present. Springs have been added to the drive train between the actuator and load to imitate this natural compliance. The majority of these springs have been in series between the actuator and load. However, a more biologically inspired approach is taken, here springs have been used in parallel to oppose each other. The paper will describe the application of parallel extension springs in a robot arm in order to give it compliance. Advantages and disadvantages of this application are discussed along with various control strategies.

Control of a compliant two-axis robotic arm

It is common to make the links between actuators and robotic limbs as stiff as possible, in complete contrast to natural systems, where compliance is present. In the past, to create some compliance in a drive, springs have been added to the link between the actuator and load. Many of these springs have been in series with the drive, but recently a more 'biological' approach has been taken where two springs have been used in parallel to counteract each other. This paper describes the application of parallel extension springs in a robot arm in order to give it compliance. Advantages and disadvantages of this application are discussed, along with various control strategies.

A cluster computing implementation of a Monte Carlo simulation of a particle growth mechanism

Clusters of computers can be used together to provide a powerful computing resource. Large Monte Carlo simulations, such as those used to model particle growth, are computationally intensive and take considerable time to execute on conventional workstations. By spreading the work of the simulation across a cluster of computers, the elapsed execution time can be greatly reduced. Thus a user has apparently the performance of a supercomputer by using the spare cycles on other workstations.

Compliant Multi-electrode Micro-channel Array for Recording Afferent Nerve Activity

We have fabricated a compliant neural interface to record afferent nerve activity. Stretchable gold electrodes were evaporated on a polydimethylsiloxane (PDMS) substrate and were encapsulated using photo-patternable PDMS. The built-in microstructure of the gold film on PDMS allows the electrodes to twist and flex repeatedly, without loss of electrical conductivity. PDMS microchannels (5mm long, 100μm wide, 100μm deep) were then plasma bonded irreversibly on top of the electrode array to define five parallel-conduit implants. The soft gold microelectrodes have a low impedance of ~200kΩ at the 1kHz frequency range. Teased nerves from the L6 dorsal root of an anaesthetized Sprague Dawley rat were threaded through the microchannels. Acute tripolar recordings of cutaneous activity are demonstrated, from multiple nerve rootlets simultaneously. Confinement of the axons within narrow microchannels allows for reliable recordings of low amplitude afferents. This electrode technology promises exciting applications in neuroprosthetic devices including bladder fullness monitors and peripheral nervous system implants.

Proposal of a floating mechanism based on magnetic levitation method toward EEG-driven robotic system

We discussed a floating mechanism based on quasi-magnetic levitation method that can be attached at the endpoint of a robot arm in order to construct a novel redundant robot arm for producing compliant motions. The floating mechanism can be composed of magnets and a constraint mechanism such that the repelling force of the magnets floats the endpoint part of the mechanism stable for the guided motions. The analytical and experimental results show that the proposed floating mechanism can produce stable floating motions with small inertia and viscosity. The results also show that the proposed mechanism can detect small force applied to the endpoint part because the friction force of the mechanism is very small.

Ventilation performance in a passage between two non-parallel buildings

A great number of studies on wind conditions in passages between slab-type buildings have been conducted in the past. However, wind conditions under different structure and configuration of buildings is still unclear and studies existed still can’t provide guidance on urban planning and design, due to the complexity of buildings and aerodynamics. The aim of this paper is to provide more insight in the mechanism of wind conditions in passages. In this paper, a simplified passage model with non-parallel buildings is developed on the basis of the wind tunnel experiments conducted by Blocken et al. (2008). Numerical simulation based on CFD is employed for a detailed investigation of the wind environment in passages between two long narrow buildings with different directions and model validation is performed by comparing numerical results with corresponding wind tunnel measurements.

Emplacement mechanism of the main granite pluton of the Lavras do Sul intrusive complex, South Brazil, determined by magnetic anisotropies

Magnetic fabric and rock magnetism studies were performed on apparently isotropic granite facies from the main intrusion of the Lavras do Sul Intrusive Complex pluton (LSIC, Rio Grande do Sul, South Brazil). This intrusion is roughly circular (similar to 12 x 13.5 km), composed of alkali-calcic and alkaline granitoids, with the latter occupying the margin of the pluton. Magnetic fabrics were determined by applying both anisotropy of low-field magnetic susceptibility (AMS) and anisotropy of anhysteretic remanent magnetization (AARM). The two fabrics are coaxial. The parallelism between AMS and AARM tensors excludes the presence of a single domain (SD) effect on the AMS fabric of the granites. Several rock-magnetism experiments performed in one specimen from each sampled site show that for all sites the magnetic susceptibility is dominantly carried by ferromagnetic minerals, while mainly magnetite carries the magnetic fabrics. Lineations and foliations in the granite facies were successful determined by applying magnetic methods. Magnetic lineations are gently plunging and roughly parallel to the boundaries of the pluton facies, except at the few sites in the central facies which have a radial orientation pattern. In contrast, the magnetic foliations tend to follow the contacts between the different granite facies. They are gently outerward-dipping inside the pluton, and become either steeply southwesterly dipping or vertical towards its margin. The lack of solid-state and subsolidus deformations at outcrop scale and in thin sections precludes deformation after full crystallization of the pluton. This evidence allows us to interpret the observed magnetic fabrics as primary in origin (magmatic) acquired when the rocks were solidified as a result of processes reflecting magma flow. The foliation pattern displays a dome-shaped form for the main LSIC-pluton. However, the alkaline granites which outcrop in the southern part of the studied area have an inward-dipping foliation, and the steeply plunging magnetic lineation suggests that this area could be part of a feeder zone. The magma ascent probably occurred due to ring-diking. (C) 2008 Elsevier B.V. All rights reserved.

Metabolic profiling by ultra-performance liquid chromatography-mass spectrometry and parallel factor analysis for the determination of disease biomarkers in Eucalyptus

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

The dual pathway in action: decoupling parallel routes for CO2 production during the oscillatory electro-oxidation of methanol

As in the case of most small organic molecules, the electro-oxidation of methanol to CO2 is believed to proceed through a so-called dual pathway mechanism. The direct pathway proceeds via reactive intermediates such as formaldehyde or formic acid, whereas the indirect pathway occurs in parallel, and proceeds via the formation of adsorbed carbon monoxide (COad). Despite the extensive literature on the electro-oxidation of methanol, no study to date distinguished the production of CO2 from direct and indirect pathways. Working under, far-from-equilibrium, oscillatory conditions, we were able to decouple, for the first time, the direct and indirect pathways that lead to CO2 during the oscillatory electro-oxidation of methanol on platinum. The CO2 production was followed by differential electrochemical mass spectrometry and the individual contributions of parallel pathways were identified by a combination of experiments and numerical simulations. We believe that our report opens some perspectives, particularly as a methodology to be used to identify the role played by surface modifiers in the relative weight of both pathways-a key issue to the effective development of catalysts for low temperature fuel cells.

A Design Method for Flexure-Based Compliant Mechanisms on the Basis of Stiffness and Stress Characteristics

Geometric nonlinearities of flexure hinges introduced by large deflections often complicate the analysis of compliant mechanisms containing such members, and therefore, Pseudo-Rigid-Body Models (PRBMs) have been well proposed and developed by Howell [1994] to analyze the characteristics of slender beams under large deflection. These models, however, fail to approximate the characteristics for the deep beams (short beams) or the other flexure hinges. Lobontiu's work [2001] contributed to the diverse flexure hinge analysis building on the assumptions of small deflection, which also limits the application range of these flexure hinges and cannot analyze the stiffness and stress characteristics of these flexure hinges for large deflection. Therefore, the objective of this thesis is to analyze flexure hinges considering both the effects of large-deflection and shear force, which guides the design of flexure-based compliant mechanisms. The main work conducted in the thesis is outlined as follows. 1. Three popular types of flexure hinges: (circular flexure hinges, elliptical flexure hinges and corner-filleted flexure hinges) are chosen for analysis at first. 2. Commercial software (Comsol) based Finite Element Analysis (FEA) method is then used for correcting the errors produced by the equations proposed by Lobontiu when the chosen flexure hinges suffer from large deformation. 3. Three sets of generic design equations for the three types of flexure hinges are further proposed on the basis of stiffness and stress characteristics from the FEA results. 4. A flexure-based four-bar compliant mechanism is finally studied and modeled using the proposed generic design equations. The load-displacement relationships are verified by a numerical example. The results show that a maximum error about the relationship between moment and rotation deformation is less than 3.4% for a flexure hinge, and it is lower than 5% for the four-bar compliant mechanism compared with the FEA results.

Parallel Architectures for Many-Core Systems-On-Chip in Deep Sub-Micron Technology

Despite the several issues faced in the past, the evolutionary trend of silicon has kept its constant pace. Today an ever increasing number of cores is integrated onto the same die. Unfortunately, the extraordinary performance achievable by the many-core paradigm is limited by several factors. Memory bandwidth limitation, combined with inefficient synchronization mechanisms, can severely overcome the potential computation capabilities. Moreover, the huge HW/SW design space requires accurate and flexible tools to perform architectural explorations and validation of design choices. In this thesis we focus on the aforementioned aspects: a flexible and accurate Virtual Platform has been developed, targeting a reference many-core architecture. Such tool has been used to perform architectural explorations, focusing on instruction caching architecture and hybrid HW/SW synchronization mechanism. Beside architectural implications, another issue of embedded systems is considered: energy efficiency. Near Threshold Computing is a key research area in the Ultra-Low-Power domain, as it promises a tenfold improvement in energy efficiency compared to super-threshold operation and it mitigates thermal bottlenecks. The physical implications of modern deep sub-micron technology are severely limiting performance and reliability of modern designs. Reliability becomes a major obstacle when operating in NTC, especially memory operation becomes unreliable and can compromise system correctness. In the present work a novel hybrid memory architecture is devised to overcome reliability issues and at the same time improve energy efficiency by means of aggressive voltage scaling when allowed by workload requirements. Variability is another great drawback of near-threshold operation. The greatly increased sensitivity to threshold voltage variations in today a major concern for electronic devices. We introduce a variation-tolerant extension of the baseline many-core architecture. By means of micro-architectural knobs and a lightweight runtime control unit, the baseline architecture becomes dynamically tolerant to variations.

Design and Characterization of Curved and Spherical Flexure Hinges for Planar and Spatial Compliant Mechanisms

A flexure hinge is a flexible connector that can provide a limited rotational motion between two rigid parts by means of material deformation. These connectors can be used to substitute traditional kinematic pairs (like bearing couplings) in rigid-body mechanisms. When compared to their rigid-body counterpart, flexure hinges are characterized by reduced weight, absence of backlash and friction, part-count reduction, but restricted range of motion. There are several types of flexure hinges in the literature that have been studied and characterized for different applications. In our study, we have introduced new types of flexures with curved structures i.e. circularly curved-beam flexures and spherical flexures. These flexures have been utilized for both planar applications (e.g. articulated robotic fingers) and spatial applications (e.g. spherical compliant mechanisms). We have derived closed-form compliance equations for both circularly curved-beam flexures and spherical flexures. Each element of the spatial compliance matrix is analytically computed as a function of hinge dimensions and employed material. The theoretical model is then validated by comparing analytical data with the results obtained through Finite Element Analysis. A case study is also presented for each class of flexures, concerning the potential applications in the optimal design of planar and spatial compliant mechanisms. Each case study is followed by comparing the performance of these novel flexures with the performance of commonly used geometries in terms of principle compliance factors, parasitic motions and maximum stress demands. Furthermore, we have extended our study to the design and analysis of serial and parallel compliant mechanisms, where the proposed flexures have been employed to achieve spatial motions e.g. compliant spherical joints.