Using Feedforward Net for Direct Sequence Parallel Search Acquisition

A feedforward net that quickly determines the maximum of a set of real values and its application in direct sequence parallel search acquisition (DSPSA) are described. The net is very suitable for a VLSI implementation due to its primary feedforward structure.

Prime Box Parallel Search Algorithm: Searching Dynamic Dictionary in O(lg m) Time

Hashing and Trie tree data structures are among the preeminent data mining techniques considered for the ideal search. Hashing techniques have the amortized time complexity of O(1). Although in worst case, searching a hash table can take as much as θ(n) time [1]. On the other hand, Trie tree data structure is also well renowned data structure. The ideal lookup time for searching a string of length m in database of n strings using Trie data structure is O(m) [2]. In the present study, we have proposed a novel Prime Box parallel search algorithm for searching a string of length m in a dictionary of dynamically increasing size, with a worst case search time complexity of O(log2m). We have exploited parallel techniques over this novel algorithm to achieve this search time complexity. Also this prime Box search is independent of the total words present in the dictionary, which makes it more suitable for dynamic dictionaries with increasing size.

A Parallel Search System for Dynamic Multi-Objective Traveling Salesman Problem

This paper introduces a parallel search system for dynamic multi-objective traveling salesman problem. We design a multi-objective TSP in a stochastic dynamic environment. This dynamic setting of the problem is very useful for routing in ad-hoc networks. The proposed search system first uses parallel processors to identify the extreme solutions of the search space for each ofk objectives individually at the same time. These solutions are merged into the so-called hit-frequency matrix E. The solutions in E are then searched by parallel processors and evaluated for dominance relationship. The search system is implemented in two different ways master-worker architecture and pipeline architecture.

Topology Search of 3-DOF Translational Parallel Manipulators with Three Identical Limbs for Leg Mechanisms

Three-degree of freedom（3-DOF） translational parallel manipulators（TPMs） have been widely studied both in industry and academia in the past decades. However, most architectures of 3-DOF TPMs are created mainly on designers＇ intuition, empirical knowledge, or associative reasoning and the topology synthesis researches of 3-DOF TPMs are still limited. In order to find out the atlas of designs for 3-DOF TPMs, a topology search is presented for enumeration of 3-DOF TPMs whose limbs can be modeled as 5-DOF serial chains. The proposed topology search of 3-DOF TPMs is aimed to overcome the sensitivities of the design solution of a 3-DOF TPM for a LARM leg mechanism in a biped robot. The topology search, which is based on the concept of generation and specialization in graph theory, is reported as a step-by-step procedure with desired specifications, principle and rules of generalization, design requirements and constraints, and algorithm of number synthesis. In order to obtain new feasible designs for a chosen example and to limit the search domain under general considerations, one topological generalized kinematic chain is chosen to be specialized. An atlas of new feasible designs is obtained and analyzed for a specific solution as leg mechanisms. The proposed methodology provides a topology search for 3-DOF TPMs for leg mechanisms, but it can be also expanded for other applications and tasks.

A Multiple-Neighborhood-Based Parallel Composite Local Search Algorithm for Timetable Problem

This paper presents a parallel composite local search algorithm based on multiple search neighborhoods to solve a special kind of timetable problem. The new algorithm can also effectively solve those problems that can be solved by general local search algorithms. Experimental results show that the new algorithm can generate better solutions than general local search algorithms.

Performance Characterization of Parallel Game-tree Search Application Crafty

Game-tree search plays an important role in the field of Artificial Intelligence （AI）. In this paper, we characterize one parallel game-tree search workload in chess： the latest version of Crafty, a state of art program, on two Intel Xeon shared-memory multiprocessor systems. Our analysis shows that Crafty is latency-sensitive and the hash-table and dynamic tree splitting used in Crafty cause large scalability penalties. They consume 35%-50% of the running time on the 4-way system. Furthermore, Crafty is not bandwidth-limited.

Parallel Multiple Tabu Search for Multiobjective Urban Transit Scheduling Problem

Urban Transit Scheduling Problem (UTSP) is concerned with determining reliable transit schedules for buses and drivers by considering the preferences of both passengers and operators based on the demand and the set of transit routes. This paper considered a UTSP which consisted of frequency setting, timetabling, and simultaneous bus and driver scheduling. A mixed integer multiobjective model was constructed to optimize the frequency of the routes by minimizing the number of buses, passenger’s waiting times and overcrowding. The model was further extended by incorporating timeslots in determining the frequencies during peak and off-peak hours throughout the time period. The timetabling problem studied two different scenarios which reflected the preferences of passengers and operators to assign the bus departure times at the first and last stop of a route. A set covering model was then adopted to minimize the number of buses and drivers simultaneously. A parallel tabu search algorithm was proposed to solve the problem by modifying the initialization process and incorporating intensification and diversification approaches to guide the search effectively from the different feasible domain in finding optimal solutions with lesser computational effort. Computational experiments were conducted on the well-known Mandl’s and Mumford’s benchmark networks to assess the effectiveness of the proposed algorithm. Competitive results are reported based on the performance metrics, as compared to other algorithms from the literature.

A Parallel String Searching Algorithm for Information Filtering

Playing an increasingly important role in the security protection of the network information systems,the intrusion detection system(IDS) becomes a hotspot of research interest nowadays.However,this technology in the kernel to many of these systems,namely string searching algorithm,has not received enough attention.By utilizing the concurrent mechanisms(multi-threading) provided by modern operation systems,such work can be divided symmetrically and thus improve the throughput of the corresponding application effectively.Presented in this work is a paralleled string searching algorithm-PBM,an algorithm based on the famous Boyer-Moore(BM) string searching algorithm.Taken as a dividable process,the string searching work is distributed between many cooperating threads of execution in the PBM algorithm,while each of them searches the target pattern in their respective share of the target strings.As compared with the traditional string searching algorithms,the PBM algorithm can do the pattern matching work faster by increasing the data processing throughput,thus adapting better to the drastic increase in the network band width.A simplification of the PBM algorithm that can be used as a multi-string searching algorithm is also suggested with supporting simulations,which is a promising approach when the number of target patterns is limited.

基于Delaunay三角网的克里金并行算法优化

当采样点数据量较大时,可以采用Delaunay三角剖分建立三角网来使用局部邻域采样点进行克里金插值.但是该算法需要对每个插值点拟合半变异函数,插值点规模大时造成巨大开销.为此,本文提出了一种以三角形为单位拟合半变异函数的克里金插值方法,采用CPU-GPU负载均衡将部分计算优化,充分考虑不均匀样本对克里金插值效果的影响.结果表明,本文算法能够保证不均匀样本集的插值效果,提升了计算性能且能够保证较高的精度.

Parallel Quick Search Algorithm for the Exact String Matching Problem Using OpenMP

String matching is seen as one of the essential problems in computer science. A variety of computer applications provide the string matching service for their end users. The remarkable boost in the number of data that is created and kept by modern computational devices influences researchers to obtain even more powerful methods for coping with this problem. In this research, the Quick Search string matching algorithm are adopted to be implemented under the multi-core environment using OpenMP directive which can be employed to reduce the overall execution time of the program. English text, Proteins and DNA data types are utilized to examine the effect of parallelization and implementation of Quick Search string matching algorithm on multi-core based environment. Experimental outcomes reveal that the overall performance of the mentioned string matching algorithm has been improved, and the improvement in the execution time which has been obtained is considerable enough to recommend the multi-core environment as the suitable platform for parallelizing the Quick Search string matching algorithm.

考虑运输时间的混合流水车间绿色生产调度

针对运输时间对混合流水车间绿色生产调度的影响这一问题,以最大完工时间、生产能耗及生产成本为优化目标,提出一种改进的多目标麻雀搜索算法(Improved Multi-Objective Sparrow Search Algorithm,IMOSSA)进行求解,参考非支配排序将种群适应度值进行划分、引入正余弦策略提高解集质量、加入多项式变异算子和Levy飞行,提高解集的收敛速度和全局搜索能力,避免陷入局部最优。而后设计16种测试算例,将IMOSSA与其他多目标优化算法进行对比,验证了IMOSSA求解的优越性。最后,以某实际生产车间为例,将其生产调度划分为4种模式,证明算法求解的实用性。

Parallel Minimax Searching Algorithm for Extremum of Unimodal Unbounded Function

In this paper we consider a parallel algorithm that detects the maximizer of unimodal function f(x) computable at every point on unbounded interval (0, ∞). The algorithm consists of two modes: scanning and detecting. Search diagrams are introduced as a way to describe parallel searching algorithms on unbounded intervals. Dynamic programming equations, combined with a series of liner programming problems, describe relations between results for every pair of successive evaluations of function f in parallel. Properties of optimal search strategies are derived from these equations. The worst-case complexity analysis shows that, if the maximizer is located on a priori unknown interval (n-1], then it can be detected after cp(n)=「2log「p/2」+1(n+1)」-1 parallel evaluations of f(x), where p is the number of processors.

提升PD效率的粒子对方法及信息传递接口并行方法

为了避免近场动力方法中粒子间物理信息重复求解消耗的计算成本和占据的额外内存,克服近场动力学低效率计算过程对其工程应用的制约,本文提出一种提升PD计算效率的粒子对方法并建立了该方法的信息传递接口并行方法。利用粒子对方法的信息传递接口并行策略并分析其计算效率的优越性,通过大型的工程应用实例给出了本文方法的工程实用性。研究结果表明:粒子对方法的应用不仅提升了计算效率,也优化了邻域粒子信息储存数组占据的内存和计算时间,粒子对方法可与信息传递接口并行编程相结合,能够进一步提升其计算效率,并且在较多线程并行时,计算效率高于OpenMP并行方法,而在实际计算中,加速效果也会受到不同线程间的通信任务影响。

甩挂运输中牵引车与挂车数量配置优化仿真

牵引车与挂车数量合理配置是道路甩挂运输中的重要内容,对提高牵引车使用效率、降低车辆的购置费用具有重要意义。以牵引车购置费用、牵引车运行费用以及牵引车等待时间费用最小为目标,考虑甩挂运输任务时间窗约束和牵引车运行径路约束,构建了上述问题的数学规划模型。针对牵引车与挂车数量配比问题的组合爆炸特点,设计了结合模拟退火邻域搜索策略的并行蚁群搜索算法。最后以郑州市某个物流企业进行实例分析,结果表明所提方法能够在较短时间内获得满意解,有效地减少了整个甩挂运输系统的综合成本。

Distributed and Parallel Component Library

Software component library is the essential part of reuse-based softwaredevelopment. It is shown that making use of a single component library to store all kinds ofcomponents and from which components are searched is very inefficient. We construct multi-librariesto support software reuse and use PVM as development environments to imitate large-scale computer,which is expected to fulfill distributed storage and parallel search of components efficiently andimprove software reuse.

面向离散粒子多尺度分析CPU/GPU架构的并行近邻搜索算法

离散粒子法在解决前沿科学和工程领域中的复杂多尺度问题中具有广泛的应用。针对离散粒子大规模多尺度计算中相邻粒子对搜索过程计算复杂度显著增加和并发度下降的问题,提出了一种适用于众核架构(CPU/GPU)的高并发、低内存占用并行近邻搜索算法。通过提出一种基于多层嵌套网格概念的层间相互作用方法,解决了不同层级间粒子对相互搜索时的数据竞争问题;通过引入非对称映射方法,避免了粒子在多级链表上的全映射,降低了内存消耗。一系列数值实验表明,该算法可有效处理108量级粒子体积跨度变化的多尺度问题,相较于传统算法可取得2~8倍的加速效果和更低的内存消耗特性,基于GPU的算法实现可达到当前领先的计算效率。

基于种群混合迁移策略的并行量子遗传算法

针对量子遗传算法求解大规模优化问题存在收敛速度慢、易于陷入局部最优等问题,改进量子遗传算法。设计一种种群混合迁移机制促进算法的种群多样性,采用仿TriBA种群结构、双精英种群、重生种群、自适应迁移算子、个体竞争排挤算子以及随机失活机制,提高算法的局部勘测能力和全局寻优能力。利用Spark框架实现算法在分布式集群环境下的运算。改进2-opt&R优化算法,通过引入高斯变异提高算法的局部搜索能力,缩小算法的搜索空间。实验结果表明,改进后的算法在全局优化能力、收敛速度、运行速度和求解稳定性等方面均有大幅度提升。

PCSS-SC下基于并行导频序列的一种主动式RAKE接收技术

为解决并行组合扩频散射传输系统信道中存在的严重多径衰落效应,提出一种基于并行导频序列的主动式RAKE接收技术。该技术利用扩频序列PN的自相关特性,添加额外并行扩频序列作为收发已知的导频信号,设计适用在并行组合扩频散射通信的系统模型,并提出该模型下的多径搜索和时延估计方法,利用散射信道相干时间减少导频序列占比。通过仿真对比分析,在SNR=-8 dB时,信号识别概率能达到90%以上,低信噪比范围内,相比无抗多径技术可以提升60%左右的正确识别概率;区分充分多径和不充分多径进行系统误码率性能仿真分析,在SNR>-2 dB的区间内,相比无抗多径技术误码率大小均降低了三个数量级以上。结果说明文中技术能有效地对抗系统存在的多径衰落,保持较好的工作性能,保证数据稳定传输。

基于混合人工蜂群算法的并行测试任务优化研究

并行测试技术可以同时进行多个任务的测试,提高资源利用率,节约测试成本;并行测试调度问题是一种复杂的组合优化问题,是并行测试技术的核心要素;并行测试系统作为并行测试技术的载体,自身的性能和求解效率尤其重要;文章对并行测试完成时间极限定理进行了研究,建立了并行测试任务调度的数学模型,分析了传统元启发式算法求解并行测试问题的不足,提出了基于动态规划的递归搜索技术和人工蜂群算法相结合的混合人工蜂群算法,并采用整数规划精确算法和遗传算法对混合人工蜂群算法进行验证;得出结论采用混合人工蜂群算法进行并行测试任务的调度节约了接近50%的时间,降低了约20%的硬件资源占用,提高了测试效率,可以满足工程实际的应用。

3轨式横向对称分布6-PSS并联机构及性能优化

针对多滑块共轨式6-PSS并联机构存在的姿态工作空间小、容易奇异等问题,课题组提出一种3轨式分布的6-PSS并联机构(P为移动副,S为球副)。该并联机构杆件长度和轨道间距呈不均匀布置,以提升姿态工作空间;采用闭环矢量法进行位置分析,通过极限边界搜索法求解工作空间;基于运动/力传递指标对机构性能进行评估,并采用性能图谱法基于全域指标GTI进行机构尺寸优化。结果表明优化后机构运动/力传递性能有显著提升,同时姿态工作空间也得到提升。该机构在工程上有一定的实用性。