GOTOBLAS一般矩阵乘法高效实现机制的研究

对GOTOBLAS库(GOTO)的实现机制,尤其是其中的一般矩阵乘法部分的实现进行了分析.结合近年来的一些研究成果,讨论了如何高效地实现矩阵相乘操作,把存储层次对程序性能的影响提高到计算模型的高度.对比实验表明,GOTO库的性能远远高于没有考虑存储层次的一般BLAS库.证明了GOTO库性能上的优越性和将存储层次引入计算模型的必要性.

Scheduling trains as a blocking parallel-machine job shop scheduling problem

In this paper, the train scheduling problem is modelled as a blocking parallel-machine job shop scheduling (BPMJSS) problem. In the model, trains, single-track sections and multiple-track sections, respectively, are synonymous with jobs, single machines and parallel machines, and an operation is regarded as the movement/traversal of a train across a section. Due to the lack of buffer space, the real-life case should consider blocking or hold-while-wait constraints, which means that a track section cannot release and must hold the train until next section on the routing becomes available. Based on literature review and our analysis, it is very hard to find a feasible complete schedule directly for BPMJSS problems. Firstly, a parallel-machine job-shop-scheduling (PMJSS) problem is solved by an improved shifting bottleneck procedure (SBP) algorithm without considering blocking conditions. Inspired by the proposed SBP algorithm, feasibility satisfaction procedure (FSP) algorithm is developed to solve and analyse the BPMJSS problem, by an alternative graph model that is an extension of the classical disjunctive graph models. The proposed algorithms have been implemented and validated using real-world data from Queensland Rail. Sensitivity analysis has been applied by considering train length, upgrading track sections, increasing train speed and changing bottleneck sections. The outcomes show that the proposed methodology would be a very useful tool for the real-life train scheduling problems

Scheduling Trains with Priorities : a no-wait blocking parallel-machine job-shop scheduling model

The paper investigates train scheduling problems when prioritised trains and non-prioritised trains are simultaneously traversed in a single-line rail network. In this case, no-wait conditions arise because the prioritised trains such as express passenger trains should traverse continuously without any interruption. In comparison, non-prioritised trains such as freight trains are allowed to enter the next section immediately if possible or to remain in a section until the next section on the routing becomes available, which is thought of as a relaxation of no-wait conditions. With thorough analysis of the structural properties of the No-Wait Blocking Parallel-Machine Job-Shop-Scheduling (NWBPMJSS) problem that is originated in this research, an innovative generic constructive algorithm (called NWBPMJSS_Liu-Kozan) is proposed to construct the feasible train timetable in terms of a given order of trains. In particular, the proposed NWBPMJSS_Liu-Kozan constructive algorithm comprises several recursively-used sub-algorithms (i.e. Best-Starting-Time-Determination Procedure, Blocking-Time-Determination Procedure, Conflict-Checking Procedure, Conflict-Eliminating Procedure, Tune-up Procedure and Fine-tune Procedure) to guarantee feasibility by satisfying the blocking, no-wait, deadlock-free and conflict-free constraints. A two-stage hybrid heuristic algorithm (NWBPMJSS_Liu-Kozan-BIH) is developed by combining the NWBPMJSS_Liu-Kozan constructive algorithm and the Best-Insertion-Heuristic (BIH) algorithm to find the preferable train schedule in an efficient and economical way. Extensive computational experiments show that the proposed methodology is promising because it can be applied as a standard and fundamental toolbox for identifying, analysing, modelling and solving real-world scheduling problems.

Almost Stable Matchings by Truncating the Gale–Shapley Algorithm

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2 + ε)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.

An algorithm for arranging response surface designs in small blocks

We consider the problem of blocking response surface designs when the block sizes are prespecified to control variation efficiently and the treatment set is chosen independently of the block structure. We show how the loss of information due to blocking is related to scores defined by Mead and present an interchange algorithm based on scores to improve a given blocked design. Examples illustrating the performance of the algorithm are given and some comparisons with other designs are made. (C) 2000 Elsevier B.V. B.V. All rights reserved.

Causes of resistant hypertension detected by a standardized algorithm

Resistant hypertension (RH) is characterized by blood pressure above 140 × 90 mm Hg, despite the use, in appropriate doses, of three antihypertensive drug classes, including a diuretic, or the need of four classes to control blood pressure. Resistant hypertension patients are under a greater risk of presenting secondary causes of hypertension and may be benefited by therapeutical approach for this diagnosis. However, the RH is currently little studied, and more knowledge of this clinical condition is necessary. In addition, few studies had evaluated this issue in emergent countries. Therefore, we proposed the analysis of specific causes of RH by using a standardized protocol in Brazilian patients diagnosed in a center for the evaluation and treatment of hypertension. The management of these patients was conducted with the application of a preformulated protocol which aimed at the identification of the causes of resistant hypertension in each patient through management standardization. The data obtained suggest that among patients with resistant hypertension there is a higher prevalence of secondary hypertension, than that observed in general hypertensive ones and a higher prevalence of sleep apnea as well. But there are a predominance of obesity, noncompliance with diet, and frequent use of hypertensive drugs. These latter factors are likely approachable at primary level health care, since that detailed anamneses directed to the causes of resistant hypertension are applied. © 2012 Livia Beatriz Santos Limonta et al.