Particle-in-Cell algorithms for emerging computer architectures

We have designed Particle-in-Cell algorithms for emerging architectures. These algorithms share a common approach, using fine-grained tiles, but different implementations depending on the architecture. On the GPU, there were two different implementations, one with atomic operations and one with no data collisions, using CUDA C and Fortran. Speedups up to about 50 compared to a single core of the Intel i7 processor have been achieved. There was also an implementation for traditional multi-core processors using OpenMP which achieved high parallel efficiency. We believe that this approach should work for other emerging designs such as Intel Phi coprocessor from the Intel MIC architecture.     

Fast computation of computer-generated hologram using Xeon Phi coprocessor

We report fast computation of computer-generated holograms (CGHs) using Xeon Phi coprocessors, which have massively x86-based processors on one chip, recently released by Intel. CGHs can generate arbitrary light wavefronts, and therefore, are promising technology for many applications: for example, three-dimensional displays, diffractive optical elements, and the generation of arbitrary beams. CGHs incur enormous computational cost. In this paper, we describe the implementations of several CGH generating algorithms on the Xeon Phi, and the comparisons in terms of the performance and the ease of programming between the Xeon Phi, a CPU and graphics processing unit (GPU).     

Quadratic optimization fine tuning for the Support Vector Machines learning phase

This work presents a comparative analysis of specific, rather than general, mathematical programming implementation techniques of the quadratic optimization problem (QP) based on Support Vector Machines (SVM) learning process. Considering the Karush–Kuhn–Tucker (KKT) optimality conditions, we present a strategy of implementation of the SVM-QP following three classical approaches: (i) active set, also divided in primal and dual spaces, methods, (ii) interior point methods and (iii) linearization strategies. We also present the general extension to treat large-scale applications consisting in a general decomposition of the QP problem into smaller ones, conserving the exact solution approach. In the same manner, we propose a set of heuristics to take into account for a better than a random selection process for the initialization of the decomposition strategy. We compare the performances of the optimization strategies using some well-known benchmark databases.     

An integrated job release and scheduling approach on parallel machines: An application in electric wire-harness industry

This paper presents a new job release (JR) and scheduling methodology for one-stage parallel machines where sequence dependent setup times exist. A decision support system (DSS) based on job release is developed in order to enable the application of the methodology. First, mathematical programming models for both job release and job scheduling are devised. Then, due to the NP-hard nature of the problems, heuristics are proposed. As for the interaction between JR and scheduling, job scheduling is integrated with job release for the proposed heuristic solutions so that the capacity achievement provided by scheduling can be utilized for job release. In brief, product design characteristics oriented scheduling affects JR in the proposed approach. Moreover, value stream mapping (VSM) approach is used with the aim of stating the effect of the proposed methodology. Furthermore, the presented methodology was applied in a real life electric wire-harness production system. The application, based on 120-day production data, revealed that the proposed methodology provided 25% decrease in in-plant manufacturing lead time.     

Tri-pyramid Robot: Design and kinematic analysis of a 3-DOF translational parallel manipulator

3-DOF translational parallel manipulators have been developed in many different forms, but they still have respective disadvantages in different applications. To overcome their disadvantages, the structure and constraint design of a 3-DOF translational parallel manipulator is presented and named the Tri-pyramid Robot. In the constraint design of the presented manipulator, a conical displacement subset is defined based on displacement group theory. A triangular pyramidal constraint is presented and applied in the constraint designs between the manipulator?s subchains. The structural properties including the decoupled motions, overconstraint elimination, singularity free workspace, fixed actuators and isotropic configuration are analyzed and compared to existing structures. The Tri-pyramid Robot is constrained and realized by a minimal number of 1-DOF joints. The kinematic position solutions, workspace with variation of structural parameters, Jacobian matrix, isotropic and dexterity analysis are performed and evaluated in the numerical simulations.     

Kokkos: Enabling manycore performance portability through polymorphic memory access patterns

The manycore revolution can be characterized by increasing thread counts, decreasing memory per thread, and diversity of continually evolving manycore architectures. High performance computing (HPC) applications and libraries must exploit increasingly finer levels of parallelism within their codes to sustain scalability on these devices. A major obstacle to performance portability is the diverse and conflicting set of constraints on memory access patterns across devices. Contemporary portable programming models address manycore parallelism (e.g., OpenMP, OpenACC, OpenCL) but fail to address memory access patterns. The Kokkos C++ library enables applications and domain libraries to achieve performance portability on diverse manycore architectures by unifying abstractions for both fine-grain data parallelism and memory access patterns. In this paper we describe Kokkos’ abstractions, summarize its application programmer interface (API), present performance results for unit-test kernels and mini-applications, and outline an incremental strategy for migrating legacy C++ codes to Kokkos. The Kokkos library is under active research and development to incorporate capabilities from new generations of manycore architectures, and to address a growing list of applications and domain libraries.     

A parallel algorithm with enhancements via partial objective value cuts for cluster-based wireless sensor network design

In this paper, we develop a parallel algorithm for the solution of an integrated topology control and routing problem in Wireless Sensor Networks (WSNs). After presenting a mixed-integer linear optimization formulation for the problem, for its solution, we develop an effective parallel algorithm in a Master–Worker model that incorporates three parallelization strategies, namely low-level parallelism, domain decomposition, and multiple search (both cooperative and independent) in a single Master–Worker framework.     

Modeling and solving mixed-model assembly line balancing problem with setups. Part I: A mixed integer linear programming model

This paper is the first one of the two papers entitled “modeling and solving mixed-model assembly line balancing problem with setups”, which has the aim of developing the mathematical programming formulation of the problem and solving it with a hybrid meta-heuristic approach. In this current part, a mixed-integer linear mathematical programming (MILP) model for mixed-model assembly line balancing problem with setups is developed. The proposed MILP model considers some particular features of the real world problems such as parallel workstations, zoning constraints, and sequence dependent setup times between tasks, which is an actual framework in assembly line balancing problems. The main endeavor of Part-I is to formulate the sequence dependent setup times between tasks in type-I mixed-model assembly line balancing problem. The proposed model considers the setups between the tasks of the same model and the setups because of the model switches in any workstation. The capability of our MILP is tested through a set of computational experiments. Part-II tackles the problem with a multiple colony hybrid bees algorithm. A set of computational experiments is also carried out for the proposed approach in Part-II.     

时间Petri网与CAGA算法相结合的并行测试研究

在并行测试的研究中对于任务的测试次序一直是个研究重点及难题。用时间Petri网建立关于并行测试系统的模型,并首次用元胞遗传算法(CAGA)对模型中的变迁序列进行搜索,快速得到最好的测试序列。通过仿真结果表明,该算法展示了很好的收敛效果,并且与已有的研究成果相比更具优势。     

基于MPI高性能计算的方法研究

并行处理在计算能力方面与单处理器的串行处理相比有着无可比拟的优势。个人计算机和网络成本的下降使得使用分布式系统进行并行处理的现象越来越普遍,而分布式网络系统中多采用MPI作为并行编程标准。为了减少程序运行时间,改善MPI计算的性能,负载均衡方法尤为重要,本文提出一种在MPI并行处理中负载均衡的方法,可以按照节点的计算能力和负载情况,在节点之间分配和迁移任务。实验表明,本文提出的方法可有效提高MPI并行处理的性能。