并行计算思考----回溯法求解数独问题

简介:  1.Intel Parallel Studio 环境下的并行程序设计 书官方网站的详情页: http://www.wrox.com/WileyCDA/WroxTitle/Parallel-Programming-with-Intel-Parallel-Studio-XE.




1.Intel Parallel Studio 环境下的并行程序设计

书官方网站的详情页:

可以下载相关代码


2.在使用并行计算来优化自己的串行程序之前,我们需要思考以下几个方面的问题
什么情况下需要并行?
并行能够带来多少性能的提升?
编码和调试的时间成本?
(串行代码早都搞出来了,并行搞出来的还不一定对,并行时间上的提升是否能够低效开发并行程序的人力资源成本?)



两个计算期望的加速比经常用到的定理Amdahl定理,和Gaustafson定理


理论上认为对于并行计算中的可扩展性(Scalability),一个程序的加速比随着处理器核数增加而变化的情况,一个完美的可扩展程序在一个四核计算机上应该是双核计算机的两倍速度。


3.实验:

并行回溯法计算数独(可能需要Intel的编译器)
资源:


编译的时候要打开vs 的openMP选项:

串行算法:可以看到速度非常快:



书上的串行算法:
openmp并行算法:

相关文章
|
14天前
|
算法
【动态规划专栏】专题一:斐波那契数列模型--------3.最小花费爬楼梯
【动态规划专栏】专题一:斐波那契数列模型--------3.最小花费爬楼梯
36 2
|
29天前
|
算法
算法修炼-动态规划之斐波那契数列模型
算法修炼-动态规划之斐波那契数列模型
|
4月前
|
算法 数据安全/隐私保护 决策智能
【算法训练-回溯算法 零】回溯算法解题框架
【算法训练-回溯算法 零】回溯算法解题框架
43 0
|
4月前
|
算法
【算法学习】—n皇后问题(回溯法)
【算法学习】—n皇后问题(回溯法)
|
10月前
|
机器学习/深度学习 算法 Python
Python实现回溯算法求解括号生成
Python实现回溯算法求解括号生成
40 0
|
10月前
|
Java
【回溯法】求解多种组合问题【java实现】
【回溯法】求解多种组合问题【java实现】
40 0
|
算法 测试技术
分治法解二维的最近对问题,算法分析与代码实现,蛮力法与分治法解决二维的最近对问题的区别
分治法解二维的最近对问题,算法分析与代码实现,蛮力法与分治法解决二维的最近对问题的区别
247 0
|
存储 算法 Python
秒懂算法 | 子集树模型——0-1背包问题的回溯算法及动态规划改进
给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为W。一种物品要么全部装入背包,要么全部不装入背包,不允许部分装入。装入背包的物品的总重量不超过背包的容量。问应如何选择装入背包的物品,使得装入背包中的物品总价值最大?
317 0
秒懂算法 | 子集树模型——0-1背包问题的回溯算法及动态规划改进
|
算法
动态规划---数字三角形模型(二)
AcWing算法提高课内容,本文讲解 动态规划
76 0
动态规划---数字三角形模型(二)
|
算法
动态规划---数字三角形模型(一)
AcWing算法提高课内容,本文讲解 动态规划
92 0
动态规划---数字三角形模型(一)