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.

Asymmetrical three-DOFs rotational-translational parallel-kinematics mechanisms based on lie group theory

The paper introduces four families of three-DOFs translational-rotational Parallel-Kinematics Mechanisms (PKMs) as well as the mobility analysis of such families using Lie group theory. Two of these families are mechanisms with one-rotational two-translational degrees of freedom (DOFs) and each of the other two has one-translational two-rotational DOFs. Four novel mechanisms are presented and discussed as representatives of these four families. Although these mechanisms are asymmetric, the components used to realise them are very similar and, hence, there is no great departure from the favourable modularity of parallel-kinematics mechanisms.

A method for extending planar axis-symmetric parallel manipulators to spatial mechanisms

This paper investigates axis-symmetric parallel manipulators, composed of a central base column and an arm system able to rotate around this column. The arm system includes several actuated upper arms, each connected to a manipulated platform by one or more lower arm linkages. Such manipulators feature an extensive positional workspace in relation to the manipulator footprint and equal manipulator properties in all radial half-planes defined by the common rotation-axis of the upper arms. The similarities between planar manipulators exclusively employing 2-degrees-of-freedom (2-DOF) lower arm linkages and lower mobility spatial manipulators only utilising 5-DOF lower arm linkages are analysed. The 2-DOF linkages are composed of a link with a 1-DOF hinge on both ends whilst the 5-DOF linkages utilise 3-DOF spherical joints and 2-DOF universal joints. By employing a proposed linkage substitution scheme, it is shown how a wide range of spatial axis-symmetric parallel manipulators can be derived from a limited range of planar manipulators of the same type.

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.

Curve Decomposition for Large Deflection Analysis of Fixed-Guided Beams With Application to Statically Balanced Compliant Mechanisms

Statically balanced compliant mechanisms require no holding force throughout their range of motion while maintaining the advantages of compliant mechanisms. In this paper, a postbuckled fixed-guided beam is proposed to provide the negative stiffness to balance the positive stiffness of a compliant mechanism. To that end, a curve decomposition modeling method is presented to simplify the large deflection analysis. The modeling method facilitates parametric design insight and elucidates key points on the force-deflection curve. Experimental results validate the analysis. Furthermore, static balancing with fixed-guided beams is demonstrated for a rectilinear proof-of-concept prototype.

A Kinetostatic Formulation for Load-Flow Visualization in Compliant Mechanisms

Load flow visualization, which is an important step in structural and machine assembly design may aid in the analysis and eventual synthesis of compliant mechanisms. In this paper, we present a kineto-static formulation to visualize load flow in compliant mechanisms. This formulation uses the concept of transferred forces to quantify load flow from input to the output of a compliant mechanism. The magnitude and direction of load flow in the constituent members enables functional decomposition of the compliant mechanism into (i) Constraints (C): members that are constrained to deform in a particular direction and (ii) Transmitters (T): members that transmit load to the output. Furthermore, it is shown that a constraint member and an adjacent transmitter member can be grouped together to constitute a fundamental building block known as an CT set whose load flow behavior is maximally decoupled from the rest of the mechanism. We can thereby explain the deformation behavior of a number of compliant mechanisms from literature by visualizing load flow, and identifying building blocks.

A Metric to Evaluate and Synthesize Distributed Compliant Mechanisms

Compliant mechanisms with evenly distributed stresses have better load-bearing ability and larger range of motion than mechanisms with compliance and stresses lumped at flexural hinges. In this paper, we present a metric to quantify how uniformly the strain energy of deformation and thus the stresses are distributed throughout the mechanism topology. The resulting metric is used to optimize cross-sections of conceptual compliant topologies leading to designs with maximal stress distribution. This optimization framework is demonstrated for both single-port mechanisms and single-input single-output mechanisms. It is observed that the optimized designs have lower stresses than their nonoptimized counterparts, which implies an ability for single-port mechanisms to store larger strain energy, and single-input single-output mechanisms to perform larger output work before failure.

Simplified PRBMs of spatial compliant multi-beam modules for planar motion

PRBMs (pseudo-rigid-body models) have been becoming important engineering technologies/methods in the field of compliant mechanisms to simplify the design and analysis through the use of the knowledge body of rigid-body mechanisms coupling with springs. This article addresses the PRBMs of spatial multi-beam modules for planar motion, which are composed of three or more symmetrical wire/slender beams parallel to each other where the planar twisting DOF (degree of freedom) is assumed to be very small for specific applications/loading conditions. Simplified PRBMs are firstly proposed through replacing each beam in spatial multi-beam module with a rigid-body link plus two identical spherical joints at its two ends. The characteristics factor, bending stiffness and twisting stiffness for the spherical joint are determined. Load-displacement equations are then derived for a class of spatial multi-beam modules and general spatial multi-beam modules using the virtual work principle and kinematic relationships. Finally, nonlinear FEA (finite element analysis) is employed with comparisons with the PRBMs. The present PRBMs have shown the ability to predict the primary nonlinear constraint characteristics such as load-stiffening effect, cross-axis coupling in the two primary translational directions and buckling load.

Compliant cryptologic protocols

Literally, the word compliance suggests conformity in fulfilling official requirements. The thesis presents the results of the analysis and design of a class of protocols called compliant cryptologic protocols (CCP). The thesis presents a notion for compliance in cryptosystems that is conducive as a cryptologic goal. CCP are employed in security systems used by at least two mutually mistrusting sets of entities. The individuals in the sets of entities only trust the design of the security system and any trusted third party the security system may include. Such a security system can be thought of as a broker between the mistrusting sets of entities. In order to provide confidence in operation for the mistrusting sets of entities, CCP must provide compliance verification mechanisms. These mechanisms are employed either by all the entities or a set of authorised entities in the system to verify the compliance of the behaviour of various participating entities with the rules of the system. It is often stated that confidentiality, integrity and authentication are the primary interests of cryptology. It is evident from the literature that authentication mechanisms employ confidentiality and integrity services to achieve their goal. Therefore, the fundamental services that any cryptographic algorithm may provide are confidentiality and integrity only. Since controlling the behaviour of the entities is not a feasible cryptologic goal,the verification of the confidentiality of any data is a futile cryptologic exercise. For example, there exists no cryptologic mechanism that would prevent an entity from willingly or unwillingly exposing its private key corresponding to a certified public key. The confidentiality of the data can only be assumed. Therefore, any verification in cryptologic protocols must take the form of integrity verification mechanisms. Thus, compliance verification must take the form of integrity verification in cryptologic protocols. A definition of compliance that is conducive as a cryptologic goal is presented as a guarantee on the confidentiality and integrity services. The definitions are employed to provide a classification mechanism for various message formats in a cryptologic protocol. The classification assists in the characterisation of protocols, which assists in providing a focus for the goals of the research. The resulting concrete goal of the research is the study of those protocols that employ message formats to provide restricted confidentiality and universal integrity services to selected data. The thesis proposes an informal technique to understand, analyse and synthesise the integrity goals of a protocol system. The thesis contains a study of key recovery,electronic cash, peer-review, electronic auction, and electronic voting protocols. All these protocols contain message format that provide restricted confidentiality and universal integrity services to selected data. The study of key recovery systems aims to achieve robust key recovery relying only on the certification procedure and without the need for tamper-resistant system modules. The result of this study is a new technique for the design of key recovery systems called hybrid key escrow. The thesis identifies a class of compliant cryptologic protocols called secure selection protocols (SSP). The uniqueness of this class of protocols is the similarity in the goals of the member protocols, namely peer-review, electronic auction and electronic voting. The problem statement describing the goals of these protocols contain a tuple,(I, D), where I usually refers to an identity of a participant and D usually refers to the data selected by the participant. SSP are interested in providing confidentiality service to the tuple for hiding the relationship between I and D, and integrity service to the tuple after its formation to prevent the modification of the tuple. The thesis provides a schema to solve the instances of SSP by employing the electronic cash technology. The thesis makes a distinction between electronic cash technology and electronic payment technology. It will treat electronic cash technology to be a certification mechanism that allows the participants to obtain a certificate on their public key, without revealing the certificate or the public key to the certifier. The thesis abstracts the certificate and the public key as the data structure called anonymous token. It proposes design schemes for the peer-review, e-auction and e-voting protocols by employing the schema with the anonymous token abstraction. The thesis concludes by providing a variety of problem statements for future research that would further enrich the literature.

Frequent activating FGFR2 mutations in endometrial carcinomas parallel germline mutations associated with craniosynostosis and skeletal dysplasia syndromes

Endometrial carcinoma is the most common gynecological malignancy in the United States. Although most women present with early disease confined to the uterus, the majority of persistent or recurrent tumors are refractory to current chemotherapies. We have identified a total of 11 different FGFR2 mutations in 3/10 (30%) of endometrial cell lines and 19/187 (10%) of primary uterine tumors. Mutations were seen primarily in tumors of the endometrioid histologic subtype (18/115 cases investigated, 16%). The majority of the somatic mutations identified were identical to germline activating mutations in FGFR2 and FGFR3 that cause Apert Syndrome, Beare-Stevenson Syndrome, hypochondroplasia, achondroplasia and SADDAN syndrome. The two most common somatic mutations identified were S252W (in eight tumors) and N550K (in five samples). Four novel mutations were identified, three of which are also likely to result in receptor gain-of-function. Extensive functional analyses have already been performed on many of these mutations, demonstrating they result in receptor activation through a variety of mechanisms. The discovery of activating FGFR2 mutations in endometrial carcinoma raises the possibility of employing anti-FGFR molecularly targeted therapies in patients with advanced or recurrent endometrial carcinoma.

Massively parallel sequencing and analysis of expressed sequence tags in a successful invasive plant

Background Invasive species pose a significant threat to global economies, agriculture and biodiversity. Despite progress towards understanding the ecological factors associated with plant invasions, limited genomic resources have made it difficult to elucidate the evolutionary and genetic factors responsible for invasiveness. This study presents the first expressed sequence tag (EST) collection for Senecio madagascariensis, a globally invasive plant species. Methods We used pyrosequencing of one normalized and two subtractive libraries, derived from one native and one invasive population, to generate an EST collection. ESTs were assembled into contigs, annotated by BLAST comparison with the NCBI non-redundant protein database and assigned gene ontology (GO) terms from the Plant GO Slim ontologies. Key Results Assembly of the 221 746 sequence reads resulted in 12 442 contigs. Over 50 % (6183) of 12 442 contigs showed significant homology to proteins in the NCBI database, representing approx. 4800 independent transcripts. The molecular transducer GO term was significantly over-represented in the native (South African) subtractive library compared with the invasive (Australian) library. Based on NCBI BLAST hits and literature searches, 40 % of the molecular transducer genes identified in the South African subtractive library are likely to be involved in response to biotic stimuli, such as fungal, bacterial and viral pathogens. Conclusions This EST collection is the first representation of the S. madagascariensis transcriptome and provides an important resource for the discovery of candidate genes associated with plant invasiveness. The over-representation of molecular transducer genes associated with defence responses in the native subtractive library provides preliminary support for aspects of the enemy release and evolution of increased competitive ability hypotheses in this successful invasive. This study highlights the contribution of next-generation sequencing to better understanding the molecular mechanisms underlying ecological hypotheses that are important in successful plant invasions.

Falls in Parkinson’s disease : evidence for altered stepping strategies on compliant surfaces

Background: Real-world environments comprise surfaces of different textures, densities and gradients, which can threaten postural stability and increase falls risk. However, there has been limited research that has examined how walking on compliant surfaces influences gait and postural stability in older people and PD patients. Methods: PD patients (n = 49) and age-matched controls (n = 32) were assessed using three dimensional motion analysis during self-paced walking on both firm and foam walkways. Falls were recorded prospectively over 12 months using daily falls calendars. Results: Walking on a foam surface influenced the temporospatial characteristics for all groups, but PD fallers adopted very different joint kinematics compared with controls. PD fallers also demonstrated reduced toe clearance and had increased mediolateral head motion(relative to walking velocity) compared with control participants. Conclusions: Postural control deficits in PD fallers may impair their capacity to attenuate surface-related perturbations and control head motion. The risk of falling for PD patients may be increased on less stable surfaces.

Maintenance optimisation of a multi-state series-parallel system considering economic dependence and state-dependent inspection intervals

This paper presents a maintenance optimisation method for a multi-state series-parallel system considering economic dependence and state-dependent inspection intervals. The objective function considered in the paper is the average revenue per unit time calculated based on the semi-regenerative theory and the universal generating function (UGF). A new algorithm using the stochastic ordering is also developed in this paper to reduce the search space of maintenance strategies and to enhance the efficiency of optimisation algorithms. A numerical simulation is presented in the study to evaluate the efficiency of the proposed maintenance strategy and optimisation algorithms. The simulation result reveals that maintenance strategies with opportunistic maintenance and state-dependent inspection intervals are more cost-effective when the influence of economic dependence and inspection cost is significant. The study further demonstrates that the optimisation algorithm proposed in this paper has higher computational efficiency than the commonly employed heuristic algorithms.