如何使用openmp将我的顺序代码修改为并行？ [英] How can I modify my sequential code into parallel using openmp?
本文介绍了如何使用openmp将我的顺序代码修改为并行？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我编写了一个程序，就像24个游戏拼图一样，即从给定的整数集和目标值，我列出所有可能的数学表达式来评估该目标值。
现在，我想使用openMP修改此代码以加速程序。那么，任何人都可以帮助我修改哪些代码段以及如何进行修改？
我尝试过：
Hi, I have written a program, which works like 24 game puzzle i.e. from the given integer set and a target value, I list all the possible mathematical expressions to evaluate that target value.
Now, I want to modify this code using openMP in order to speedup the program. So, can anyone help me which code segments should be modified and how can it be done?
What I have tried:
#include <iostream>
#include <string>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
//All the Declaration of my functions
vector<int> getQuestion();
#define EMPTY -1
#define DIV 0
#define MUL 1
#define PLUS 2
#define MINUS 3
//Declare Global Constant
const string problemFile = "problem.txt";
const string answerFile = "answer.txt";
ofstream writeToAnswerFile(answerFile);
/* Following function is needed for library function qsort(). */
int compare(const void *a, const void * b)
{
return (*(int *)a - *(int *)b);
}
// A utility function two swap two characters a and b
void swap(int* a, int* b)
{
char t = *a;
*a = *b;
*b = t;
}
// This function finds the index of the smallest character
// which is greater than 'first' and is present in str[l..h]
int findCeil(int str[], int first, int l, int h)
{
// initialize index of ceiling element
int ceilIndex = l;
// Now iterate through rest of the elements and find
// the smallest character greater than 'first'
for (int i = l + 1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
void releaseAnswerFile() {
writeToAnswerFile.close();
}
//Main Program
int main() {
writeToAnswerFile<<"-1"<<endl;
writeToAnswerFile.close();
atexit(releaseAnswerFile);
vector<int> question = getQuestion(); //Retrieve Question from file
int* questionArray = new int[question.size()]();
char operatorList[] = { '/','*','+','-' };
int targetAnswer = question.back(); //Get the final answer
question.pop_back(); //remove the final answer from question list
const int numberOfOperator = question.size() - 1;
const int questionSize = question.size();
bool hasAnswer = false;
for (int i = 0; i < questionSize;i++) {
questionArray[i] = question[i];
}
if (!question.empty()) {
// Sort the string in increasing order
qsort(questionArray, questionSize, sizeof(int), compare);
//create dynamic allocation array
int* tempOperationSequence = new int[numberOfOperator]();
int* tempOperandSequence = new int[questionSize]();
//algorithm starts for operands' permutation without duplication
bool isFinished = false;
while (!isFinished)
{
////////////////////////////////////////////////
//brute force every operator combination algorithm start
bool shouldContinueFindNewOperatorCombination = true;
int* operationSequence = new int[numberOfOperator](); //initialize the operand with all value 0
operationSequence[0] = -1;
int operatorPositionToChange = 0;
bool containMultiplication = false;
do {
bool shouldSkipThisCombination = false;
//generate next set of operand's combination
if (++operationSequence[operatorPositionToChange] == 4) {
for (int i = operatorPositionToChange; i < numberOfOperator;i++) {
if (operationSequence[i] == 4) {
operationSequence[i] = 0;
if (i + 1 == numberOfOperator) {
shouldContinueFindNewOperatorCombination = false;
shouldSkipThisCombination = true;
break;
}
operationSequence[i + 1]++;
}
}
}
operatorPositionToChange = 0;
//Check Point 1
if (shouldSkipThisCombination) {
continue;
}
//Create a copy of operator array and operand array
for (int operation = 0; operation < numberOfOperator;operation++) {
tempOperationSequence[operation] = operationSequence[operation];
}
for (int operand = 0; operand < questionSize;operand++) {
tempOperandSequence[operand] = questionArray[operand];
}
//Start the calculate the answer based on current set of operators and operands
int finalResult;
int fDigitPos = 0; //First digit position
int sDigitPos = 1; //Second digit position
//check all division operators first, if there are any invalid pairs, directly discard the whole combination
for (size_t i = 0; i < numberOfOperator; i++) {
if (tempOperationSequence[i] == DIV) {
if (tempOperandSequence[i + 1] <= 0 || tempOperandSequence[i] % tempOperandSequence[i + 1] != 0) {
operatorPositionToChange = i;
shouldSkipThisCombination = true;
break;
}
}
}
//Check Point 2
if (shouldSkipThisCombination) {
continue;
}
//entering the real calculation part
//look for both multiplication and division operator
for (size_t i = 0; i < numberOfOperator && fDigitPos != numberOfOperator; i++) {
if (tempOperationSequence[i] == DIV) {
if (tempOperandSequence[sDigitPos] > 0 && tempOperandSequence[fDigitPos] % tempOperandSequence[sDigitPos] == 0) {
tempOperandSequence[fDigitPos] /= tempOperandSequence[sDigitPos];
tempOperandSequence[sDigitPos] = -1;
tempOperationSequence[i] = -1;
sDigitPos++;
}
else {
shouldSkipThisCombination = true;
break;
}
}
else if (tempOperationSequence[i] == MUL) {
tempOperandSequence[fDigitPos] *= tempOperandSequence[sDigitPos];
tempOperandSequence[sDigitPos] = -1;
tempOperationSequence[i] = -1;
sDigitPos++;
}
else {
fDigitPos = sDigitPos;
sDigitPos++;
}
}
//Check Point 3
if (shouldSkipThisCombination) {
continue;
}
fDigitPos = 0;
sDigitPos = 1;
for (int i = 0; i < numberOfOperator;i++) {
if (tempOperandSequence[i] != -1) {
fDigitPos = i;
sDigitPos = i + 1;
break;
}
}
//perform addition and subtraction
for (size_t i = 0; i < numberOfOperator &&fDigitPos != numberOfOperator; i++) {
if (tempOperationSequence[i] == EMPTY) {
continue;
}
else if (tempOperandSequence[sDigitPos] == EMPTY) {
i--;
sDigitPos++;
continue;
}
//Since plus and minus are the last section, no need to indicate used operands and operators is still ok
else if (tempOperationSequence[i] == PLUS) {
tempOperandSequence[fDigitPos] += tempOperandSequence[sDigitPos];
sDigitPos++;
}
else if (tempOperationSequence[i] == MINUS) {
tempOperandSequence[fDigitPos] -= tempOperandSequence[sDigitPos];
sDigitPos++;
}
}
//get the final result from array
finalResult = tempOperandSequence[fDigitPos];
//check result
if (finalResult == targetAnswer) {
//directly write answer into the file
if(hasAnswer){
writeToAnswerFile<<questionArray[0];
for (size_t answerPos = 1; answerPos < questionSize; answerPos++) {
writeToAnswerFile<<operatorList[operationSequence[answerPos - 1]];
writeToAnswerFile<<questionArray[answerPos];
}
}else{
hasAnswer = true;
writeToAnswerFile = ofstream(answerFile,ios::trunc);
writeToAnswerFile<<questionArray[0];
for (size_t answerPos = 1; answerPos < questionSize; answerPos++) {
writeToAnswerFile<<operatorList[operationSequence[answerPos - 1]];
writeToAnswerFile<<questionArray[answerPos];
}
}
writeToAnswerFile << endl;
}
} while (shouldContinueFindNewOperatorCombination);
delete [] operationSequence;
////////////////////////////////////////////////
// Find the rightmost character which is smaller than its next
// character. Let us call it 'first char'
int i;
for (i = questionSize - 2; i >= 0; --i)
if (questionArray[i] < questionArray[i + 1])
break;
// If there is no such chracter, all are sorted in decreasing order,
// means we just printed the last permutation and we are done.
if (i == -1)
isFinished = true;
else
{
// Find the ceil of 'first char' in right of first character.
// Ceil of a character is the smallest character greater than it
int ceilIndex = findCeil(questionArray, questionArray[i], i + 1, questionSize - 1);
// Swap first and second characters
swap(&questionArray[i], &questionArray[ceilIndex]);
// Sort the string on right of 'first char'
qsort(questionArray + i + 1, questionSize - i - 1, sizeof(int), compare);
}
}
delete[] tempOperationSequence; //release dynamic allocation memory
delete[] tempOperandSequence; //release dynamic allocation memory
writeToAnswerFile.close();
}
return 0;
}
/***
getQuestion()
- Open Problem file and retrieve all the numbers from the file
return:
- vector<int> - List of Numbers
*/
vector<int> getQuestion() {
vector<int> numbers;
string line;
ifstream opener;
opener.open(problemFile);
if (opener.is_open()) {
while (getline(opener, line))
{
numbers.push_back(stoi(line));
}
}
opener.close();
return numbers;
}</int></int></int></int></int></vector></algorithm></fstream></string></iostream>
推荐答案
使代码并行并不总是解决方案，因为它也会带来开销。你的主要任务应该是找到代码的慢速部分并重新设计它们。
我看到你经常写在writeToAnswerFile文件中。这看起来像是一个瓶颈。我会尝试将这些信息存储在字符串中并在需要时写入一次如果全部完成。
Making code parallel isnt always the solution, because it also makes overhead for that. Your primary task should be finding the slow parts of code and redesign them.
As I see you often writing in the writeToAnswerFile file. That looks like a bottleneck. I would try to store that information in a string and write if needed once if all is done.
//Create a copy of operator array and operand array
for (int operation = 0; operation < numberOfOperator;operation++) {
tempOperationSequence[operation] = operationSequence[operation];
}
我会替换
I would replace
memcpy(tempOperationSequence, operationSequence, operation);
代码中的不同位置。
并行的唯一内容是排序。谷歌了解更多信息。
on different places in your code.
The only thing for parallel is the sorting. Google for further information.
这篇关于如何使用openmp将我的顺序代码修改为并行？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
