## OpenMP多线程并行查找算法设计

Parallel Search Algorithms
Abstract: The main purpose of this thesis is to study the parallel search algorithms. As we all know, there are many search algorithms, and we can conclude different algorithms which are based on different data structure. The main topic is to research the linear search algorithms, which conclude the sequential search, binary search, block search and simple search in arrays. In order to design the parallel search algorithms, firstly, we must understand their serial search version, and we should find which part in their serial versions could happen at the same time, which means the concurrency.Secondly, the part of the design and realization is coming, by the way, we use the OpenMP multi-threaded programming in this paper. Finally, we should test and optimize the algorithms. Due to the “uncertainty” and” asynchronous” brought by concurrency, the first step is the most critical and most complex in all steps, which is directly determines the performance of the algorithm.
Keywords:    Linear Search; Concurrency; Task Decomposition 源自六"维~论`文}网"加7位QQ3249.114 www.lwfree.cn

Abstract    i

1    绪论    1
1.1    工作介绍    1
1.1.1    并行查找算法的意义    1
1.1.2    具体工作    1
1.2    多核编程遇到的问题    2
1.2.1    并发性问题    2
1.2.2    CPU饥饿    2
1.2.3    任务的分解    2
1.3    OPENMP多线程编程    3
1.3.1    OpenMP的基本概念    3
1.3.2    线程创建与工作分摊    4
1.3.3    数据处理    6
1.3.4    线程间的同步    7
1.3.5    OpenMP库函数    7
1.3.6    OpenMP环境变量    8
2    查找问题分析    9
2.1    任务分解    9
2.2    线性查找算法并行化分析    9
2.2.1    顺序查找算法    9
2.2.2    二分查找    11
2.2.3    分块查找    11
3    设计与实现    14
3.1    顺序查找算法    14
3.1.1    带重复关键字查找    14
3.1.2    关键字唯一查找    15
3.2    二分查找    16
3.2.1    第一部分：    16
3.2.2    第二部分    17 OpenMP多线程并行查找算法设计:http://www.lwfree.cn/jisuanjilunwen/20171114/15890.html
------分隔线----------------------------