Optimal scheduling of compute-intensive tasks on a network ofworkstations

In a network of high performance workstations, many workstations are underutilized by their owners. The problem of using these idle cycles for solving computationally intensive tasks by executing a large task on many workstations has been addressed before and algorithms with O(N²) time and O(N) space for choosing the optimal subset of workstations out of N workstations were presented. We improve these algorithms to reduce the running time to O(N log N), while keeping the space requirement the same. The proposed algorithms are particularly useful for SPMD parallelism where computation is the same for all workstations and the data space is partitioned between the workstations     

Parallel volume rendering on a network of workstations

An algorithm for parallel volume rendering on general-purpose workstations connected to a local area network (LAN) is presented. The algorithm is based on an efficient scan-line algorithm for volume rendering of irregular meshes. This algorithm computes images by intersecting the mesh with successive planes defined through each scan line and perpendicular to the screen. These planes are called scan planes. Image coherency from one scan plane to the next, and within each scan plane, speeds up image computation. The proposed algorithm is a modified version of the scan-line algorithm, suitable for parallelization and for handling large data sets efficiently. Based on an efficiency analysis of this version, it is concluded that minimal additional computing and communication are required if each processor is given the task of computing sequences of successive lines in the image. Ways of achieving good load balancing on a group of heterogeneous workstations that have arbitrary loads by other users are suggested     

基于混合需求的设施选址问题研究

研究网络中设施的需求一部分来自于网络节点, 一部分来自于过往流量的基于混合需求的设施选址问题。引入引力模型, 以新建设施获得总利润最大为目标建立非线性整数规划模型, 并构造启发式算法, 通过MATLAB进行仿真实验, 将求解结果与GPAH算法及精确算法的结果进行比较。比较结果表明, 提出的算法求解质量高、运行速度快, 可用于大中型网络设施的选址问题。     

Data-parallel programming on a network of heterogeneous workstations

We describe a compiler and run-time system that allow data-parallel programs to execute on a network of heterogeneous UNIX workstations. The programming language supported is Dataparallel C, a SIMD language with virtual processors and a global name space. This parallel programming environment allows the user to take advantage of the power of multiple workstations without adding any message-passing calls to the source program. Because the performance of Individual workstations in a multi-user environment may change during the execution of a Dataparallel C program, the run-time system automatically performs dynamic load balancing. We present experimental results that demonstrate the usefulness of dynamic load-balancing In a multi-user environment These results suggest that initially allocating the same amount of work to each processor and letting the dynamic load balancing algorithm adjust the load during program execution yields very good performance. Hence neither the compiler nor the run-time system need a priori knowledge of the speeds of the machines that will participate in a program execution.     

Bandwidth optimal all-reduce algorithms for clusters of workstations

We consider an efficient realization of the all-reduce operation with large data sizes in cluster environments, under the assumption that the reduce operator is associative and commutative. We derive a tight lower bound of the amount of data that must be communicated in order to complete this operation and propose a ring-based algorithm that only requires tree connectivity to achieve bandwidth optimality. Unlike the widely used butterfly-like all-reduce algorithm that incurs network contention in SMP/multi-core clusters, the proposed algorithm can achieve contention-free communication in almost all contemporary clusters, including SMP/multi-core clusters and Ethernet switched clusters with multiple switches. We demonstrate that the proposed algorithm is more efficient than other algorithms on clusters with different nodal architectures and networking technologies when the data size is sufficiently large.     

Computing the correlation dimension on a network of workstations

We present a parallel algorithm for computing the correlation dimension (D₂) from a time series generated by a dynamic system, using the method of correlation integrals, which essentially requires the computation of distances among a set of points in the state space. The parallelization is suitable for coarse-grained multiprocessor systems with distributed memory and is carried out using a virtually shared memory model. The algorithm simultaneously gives all the correlation integrals at various state space dimensions needed to estimate the D₂. Two versions are discussed: the first computes all distances between points; the second computes only distances less than a fixed ϵ, and employs a box-assisted approach and linked lists for an efficient search of neighbouring points. The algorithms, coded in Fortran 77, are tested on a heterogeneous network of workstations consisting of various DEC Alphas of different powers, interconnected by Ethernet; the Network Linda parallel environment is used. A detailed analysis of performance is carried out using the generalization of speed-up and efficiency for heterogeneous systems. The algorithms are fully asynchronous and so intrinsically balanced. In almost all the situations they provide a unitary efficiency. The second version greatly reduces the computational work, thus making it possible to tackle D₂ estimation even for medium and high-dimensional systems, where an extremely large number of points is involved. The algorithms can also be employed in other applicative contexts requiring the efficient computation of distances among a large set of points. The method proposed for the analysis of performance can be applied to similar problems. © 1998 John Wiley & Sons, Ltd.     

随机模式匹配并行算法在工作站机群上的实现

对随机模式匹配算法进行了改进,并根据MPICH并行编程环境中任务间通信的特点,设计了一种基于MPICH的改进的随机模式匹配并行算法。根据运行在COW（工作站机群）上的进程数目将文本串进行重叠划分,每个进程完成一个文本子串的模式匹配。实验结果表明,该改进的随机模式匹配并行算法有效地加快了模式匹配的速度,提高了工作站机群的资源利用率。     

A non-blocking locking method and performance evaluation on network of workstations

A network of workstation(NOW) can act as a single and scalable powerful computer by building a paralle and distributed computing platform on top of it.WAKASHI is such a platform system that supports persitent object management and makes full use of resources of NOW for high perforance transaction processing,One of the main difficulties to overcome is the bottleneck caused by concurrency control mechanism.Therefore,a non-bloking locking method is designed,by adopting several novel techniques to make it outperform the other typical locking methods such as 2PL:1) an SDG (Semantic Dependency Graph)based non-blocking locking protocol for fast transaction scheduling;2) a nmassively virtual memory based backup-page undo algorithm for fast restart;and 3) a multi-processor and multi-thread based transaction manager for fast execution.The new mechanisms have been implemented in WAKASHI and the performance comparison experiments have been implemented in WAKASHI and the performance comparison experiments with 2PL and DWDL have been done.The results show that the new method can outperform 2PL and DWDL under certain conditons.This is meaningful for choosing effective concurrency control mechanisms for improving transaction-rpocessing performance in NOW environments.     

Molecular dynamics simulation on a network of workstations using a machine-independent parallel programming language.

Molecular dynamics simulations investigate local and global motion in molecules. Several parallel computing approaches have been taken to attack the most computationally expensive phase of molecular simulations, the evaluation of long range interactions. This paper reviews these approaches and develops a straightforward but effective algorithm using the machine-independent parallel programming language, Linda. The algorithm was run both on a shared memory parallel computer and on a network of high performance Unix workstations. Performance benchmarks were performed on both systems using two proteins. This algorithm offers a portable cost-effective alternative for molecular dynamics simulations. In view of the increasing numbers of networked workstations, this approach could help make molecular dynamics simulations more easily accessible to the research community.     

Radio-wave propagation prediction using ray-tracing techniques on a network of workstations (NOW)

Ray-tracing based radio wave propagation prediction models play an important role in the design of contemporary wireless networks as they may now take into account diverse physical phenomena including reflections, diffractions, and diffuse scattering. However, such models are computationally expensive even for moderately complex geographic environments. In this paper, we propose a computational framework that functions on a network of workstations (NOW) and helps speed up the lengthy prediction process. In ray-tracing based radio propagation prediction models, orders of diffractions are usually processed in a stage-by-stage fashion. In addition, various source points (transmitters, diffraction corners, or diffuse scattering points) and different ray-paths require different processing times. To address these widely varying needs, we propose a combination of the phase-parallel and manager/workers paradigms as the underpinning framework. The phase-parallel component is used to coordinate different computation stages, while the manager/workers paradigm is used to balance workloads among nodes within each stage. The original computation is partitioned into multiple small tasks based on either raypath-level or source-point-level granularity. Dynamic load-balancing scheduling schemes are employed to allocate the resulting tasks to the workers.We also address issues regarding main memory consumption, intermediate data assembly, and final prediction generation. We implement our proposed computational model on a NOW configuration by using the message passing interface (MPI) standard. Our experiments with real and synthetic building and terrain databases show that, when no constraint is imposed on the main memory consumption, the proposed prediction model performs very well and achieves nearly linear speedups under various workload. When main memory consumption is a concern, our model still delivers very promising performance rates provided that the complexity of the involved computation is high, so that the extra computation and communication overhead introduced by the proposed model do not dominate the original computation. The accuracy of prediction results and the achievable speedup rates can be significantly improved when 3D building and terrain databases are used and/or diffuse scattering effect is taken into account.     

Models to predict efficiency of two network flow based algorithms on the Time-Cost Trade-Off problem

Two predictive models for estimating the computer execution time required by two network flow based algorithms to solve the Time-Cost Trade-Off problem are presented. Fulkerson's Longest Path Algorithm and Phillips and Dessouky's Cut Search Algorithm are used. A comparison of performance of these two algorithms for different network structures is provided.The two algorithms are coded into Fortran programs, and it is found that the solution time increases linearly with the number of nodes and several other parameters. In addition, the Longest Path Algorithm is found to be computationally more efficient than the Cut Search Algorithm in solving the Time-Cost Trade-Off problem.     

A template-based approach to the generation of distributedapplications using a network of workstations

A computational model and system for the generation of distributed applications in a workstation environment are presented. The well-known RPC model is modified by a novel concept known as template attachment. A computation consists of a network of sequential procedures which have been encapsulated in templates. A small selection of templates is available from which a distributed application with the desired communication behavior can be rapidly built. The system generates all the required low-level code for correct synchronization, communication, and scheduling. This results in a system that is easy to use and flexible and can provide a programmer with the desired amount of control in using idle processing power over a network of workstations. The practical feasibility of the model has been demonstrated by implementing it for Unix-based workstation environments     

无线传感器网络节点定位算法的研究

无线传感器网络节点数量大、资源有限,采用全球定位系统(GPS)定位设备来获取节点位置信息成本太高,研究适合无线传感器网络节点定位算法具有重要意义。通过分析无线传感器网络节点定位算法的基本原理,介绍已提出的几种节点定位算法,并进行分析比较。     

Models and algorithms for a multilevel control system of primary oil refinery installations

Algorithms and mathematical models for the technological process of primary oil refinery operating in the uncertain conditions are developed; the solution of the optimal control problem in the form of stochastic programming with probabilistic characteristics is presented. For solving the optimization problem, using the Lagrange method, the problem of development of decomposition algorithms is described and the method based on the transformation of the original problem according to the principle of deterministic analogue is proposed. The construction of the optimal control system created based on the developed models, optimization algorithm, and principles of automatic control of regime parameters of the primary oil refinery installation are considered.     

基于Web挖掘的过程模型及算法

针对Web信息的结构特点设计了一个发现用户访问模式的PDAS系统,并以关联规则为理论基础提出了发现单一用户K 序列频繁访问模式的过程模型及算法。经实验证明,通过该算法获得的频繁访问模式对商业网站的营销决策有一定辅助意义。     

Evaluation of distributed finite element algorithms on a workstation network

This paper discusses the design, implementation and evaluation of linear finite element programs that distribute their computations over a network of workstations. We consider five different algorithms based on direct, iterative and hybrid equation solvers, each of which partitions and maps the model domain across conventional network hardware. A software architecture based on the client-server model distributes the computations and, at the language level, Berkeley sockets enable communication between processes. We evaluate and describe the performance of these algorithms in terms of execution time and speed-up, and we conclude that distributed solvers, particularly those based on substructuring and static condensation, can be effective even on high-latency communication networks.     

Models,algorithms and error estimation for computational viscoelasticity

This article reviews numerical algorithms for problems in solid polymer viscoelasticity in both small and large deformation. For the linear (small strain) case we review both the quasistatic and the dynamic problem and give recent results on a posteriori error estimation. For the large strain case we focus on the formulation and computational modelling of constrained membrane inflation, the application of which is to the thermoforming process.     

Models and algorithms for computing the common labelling of a set of attributed graphs

In some methodologies, it is needed a consistent common labelling between the vertices of a graph set, for instance, to compute a representative of a set of graphs. This is an NP-complete problem with an exponential computational cost depending on the number of nodes and the number of graphs. In the current paper, we present two new methodologies to compute a sub-optimal common labelling. The former focuses in extending the Graduated Assignment algorithm, although the methodology could be applied to other probabilistic graph-matching algorithms. The latter goes one step further and computes the common labelling whereby a new iterative sub-optimal algorithm. Results show that the new methodologies improve the state of the art obtaining more precise results than the most recent method with similar computational cost.     

Some properties and algorithms for the hyper-torus network

The hyper-torus network based on a three-dimensional hypercube was introduced recently. The hyper-torus \(QT(m,n)\) performs better than mesh type networks with a similar number of nodes in terms of the network cost. In this paper, we prove that if \(n\) is even, the bisection width of \(QT(m,n)\) is \(6n\) , whereas it is \(6n+2\) if it is odd. Second, we show that \(QT(m,n)\) contains a Hamiltonian cycle. In addition, its one-to-all and all-to-all broadcasting algorithms are introduced. All of these broadcasting algorithms are asymptotically optimal.