pp #5
Description
#include
#include <omp.h>
using namespace std;
long long int fib(int n){
if(n<=1) return n;
long long int a=0,b=1,temp;
for(int i=2;i<=n;i++){
temp= a+b;
a=b;
b=temp;
}
return b;
}
int main(){
long long int result1,result2;
#pragma omp parallel
{
#pragma omp sections
{
#pragma omp section
{
result1=fib(30);
cout<<"Fibonacci(30)"<<result1;
}
}
}
return 0;
}--------------------------------------
bfs
#include
#include
#include <omp.h>
using namespace std;
class Node {
public:
vector next;
Node() {}
};
vector nodes;
vector visited;
vector level;
vector<vector > q(2); // Note the space between '>' '>'
void parallel_bfs(int start) {
visited[start] = true;
level[start] = 0;
q[0].push_back(start);
int current_queue = 0;
while (true) {
int next_queue = (current_queue + 1) % 2;
q[next_queue].clear();
omp_set_dynamic(0);
int current_node;
#pragma omp parallel private(current_node)
{
#pragma omp for
for (int i = 0; i < q[current_queue].size(); i++) {
current_node = q[current_queue][i];
for (int j = 0; j < nodes[current_node].next.size(); j++) {
int neighbor = nodes[current_node].next[j];
if (!visited[neighbor]) {
visited[neighbor] = true;
level[neighbor] = level[current_node] + 1;
#pragma omp critical
q[next_queue].push_back(neighbor);
}
}
}
}
if (q[next_queue].empty()) {
break;
} else {
current_queue = next_queue;
}
}
}
int main() {
int n, edges;
cout << "Enter number of nodes and number of edges: ";
cin >> n >> edges;
nodes.resize(n);
visited.resize(n, false);
level.resize(n, -1);
cout << "Enter the edges (format: u v) starting from 0:" << endl;
for (int i = 0; i < edges; i++) {
int u, v;
cin >> u >> v;
nodes[u].next.push_back(v);
nodes[v].next.push_back(u); // assuming undirected
}
int start_node;
cout << "Enter the start node: ";
cin >> start_node;
parallel_bfs(start_node);
cout << "\nLevels of each node from start node " << start_node << ":" << endl;
for (int i = 0; i < n; i++) {
cout << "Node " << i << ": Level " << level[i] << endl;
}
return 0;
}
histo
#include
#include
#include
#include <omp.h>
#include
#include
#define nullptr 0
const int MAX_VALUE = 100; // Max value of elements
const int NUM_THREADS = 4; // Number of threads
void distributed_histogram_sort(std::vector& data) {
int n = data.size();
std::vector global_hist(MAX_VALUE, 0);
// Step 1: Create private histograms for each thread
std::vector<std::vector<int> > local_hists(NUM_THREADS, std::vector<int>(MAX_VALUE, 0));
// Step 2: Count frequencies in parallel
#pragma omp parallel num_threads(NUM_THREADS)
{
int tid = omp_get_thread_num();
int chunk_size = n / NUM_THREADS;
int start = tid * chunk_size;
int end = (tid == NUM_THREADS - 1) ? n : start + chunk_size;
for (int i = start; i < end; ++i) {
local_hists[tid][data[i]]++;
}
}
// Step 3: Combine local histograms into global histogram
for (int i = 0; i < MAX_VALUE; ++i) {
for (int t = 0; t < NUM_THREADS; ++t) {
global_hist[i] += local_hists[t][i];
}
}
// Step 4: Prefix sum to find positions
std::vector<int> start_pos(MAX_VALUE, 0);
for (int i = 1; i < MAX_VALUE; ++i) {
start_pos[i] = start_pos[i - 1] + global_hist[i - 1];
}
// Step 5: Fill sorted array
std::vector<int> sorted_data(n);
std::vector<int> current_pos = start_pos;
#pragma omp parallel for schedule(static) num_threads(NUM_THREADS)
for (int i = 0; i < MAX_VALUE; ++i) {
for (int j = 0; j < global_hist[i]; ++j) {
int index;
#pragma omp critical
index = current_pos[i]++;
sorted_data[index] = i;
}
}
data = sorted_data; // Copy back sorted data
}
int main() {
std::srand(std::time(NULL));
int n = 1000000;
std::vector data(n);
// Fill with random values (C++98 style)
for (int i = 0; i < n; ++i) {
data[i] = std::rand() % MAX_VALUE;
}
double start = omp_get_wtime();
distributed_histogram_sort(data);
double end = omp_get_wtime();
std::cout << "Sorted " << n << " elements in " << (end - start) << " seconds.\n";
// Verify correctness
bool is_sorted = true;
for (int i = 1; i < n; ++i) {
if (data[i - 1] > data[i]) {
is_sorted = false;
break;
}
}
if (is_sorted) {
std::cout << "Data is sorted correctly!\n";
} else {
std::cout << "Sorting failed.\n";
}
return 0;
}
dijkstra
#include
#include
#include
#include <omp.h>
using namespace std;
const int INF = INT_MAX;
// Parallel Dijkstra function
void dijkstra_parallel(const vector<vector > &graph, int src, vector &dist) {
int n = graph.size();
vector visited(n, false);
dist.assign(n, INF);
dist[src] = 0;
for (int count = 0; count < n - 1; count++) {
int u = -1;
int minDist = INF;
// ?? Step 1: Find the unvisited node with the smallest distance
#pragma omp parallel for
for (int i = 0; i < n; i++) {
#pragma omp critical
{
if (!visited[i] && dist[i] < minDist) {
minDist = dist[i];
u = i;
}
}
}
if (u == -1) break; // no reachable node left
visited[u] = true;
// ?? Step 2: Update neighbors in parallel
#pragma omp parallel for
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] && dist[u] != INF &&
dist[u] + graph[u][v] < dist[v]) {
#pragma omp critical
dist[v] = dist[u] + graph[u][v];
}
}
}
}
int main() {
int n, src;
cout << "Enter number of nodes: ";
cin >> n;
vector<vector<int> > graph(n, vector<int>(n));
cout << "Enter the adjacency matrix (0 if no edge):\n";
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> graph[i][j];
cout << "Enter source node (0-based): ";
cin >> src;
vector<int> dist;
dijkstra_parallel(graph, src, dist);
cout << "\nShortest distances from node " << src << ":\n";
for (int i = 0; i < n; i++) {
if (dist[i] == INF)
cout << "Node " << i << ": Unreachable\n";
else
cout << "Node " << i << ": " << dist[i] << "\n";
}
return 0;
}
#include
#include <omp.h>
using namespace std;
#include
long dot_product(vector Vect1,vector Vect2){
unsigned long result=0.0;
#pragma omp parallel for reduction(+:result) num_threads(4)
for(int i=0;i<=Vect1.size();++i){
result+=Vect1[i]*Vect2[i];
}
return result;
}
int main(){
std::vector vec1;
std::vector vec2;
int dimension,x,y;
cout<<"enter the dimension of the vector"<<endl;
cin>>dimension;
cout<<"enter the values of coordinates of vector1 as x and vector2 as y"<<endl;
for(int i=0;i<dimension;i++){
cin>>x;
cin>>y;
vec1.push_back(x);
vec2.push_back(y);
}
unsigned long result = dot_product(vec1, vec2);
cout << "Dot product: " << result <<endl;
return 0;
}--------------------
#include
#include <omp.h>
#include
#include
using namespace std;
void QuickSort(int arr[],int left,int right){
if(left>=right)
return;
int piv=arr[right];
int i=left-1;
for(int j=left;j<right;j++){
if(arr[j]<piv){
swap(arr[++i],arr[j]);
}
}
swap(arr[i+1],arr[right]);
int parti=i+1;
#pragma omp parallel sections
{
#pragma omp section
QuickSort(arr,left,parti-1);
#pragma omp section
QuickSort(arr,parti+1,right);
}
}
int main(){
int size;
cout<<"enter size of an array";
cin>>size;
int arr[size];
srand(time(0));
for(int i=0;i<size;i++){
arr[i]=rand()%100+1;
}
cout<<"unsorted array is"<<endl;
for(int i=0;i<size;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
#pragma omp parallel
{
#pragma omp single
QuickSort(arr,0,size-1);
}
cout<<"sorted array is"<<endl;
for(int i=0;i<size;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
// Recursive Fibonacci function using OpenMP tasks
long long int fib(int n) {
if (n <= 1) return n;
long long int x, y;
#pragma omp task shared(x)
x = fib(n - 1); // Task 1: Compute fib(n-1)
#pragma omp task shared(y)
y = fib(n - 2); // Task 2: Compute fib(n-2)
#pragma omp taskwait // Ensure both tasks complete before summing
return x + y;
}
#include
#include <omp.h>
#include
#include
using namespace std;
#define ARR_SIZE 600
#define STEP_SIZE 100
int main() {
int arr[ARR_SIZE];
int i, sum = 0;
// Fill array with random numbers between 1 and 10
// srand(time(0));
srand(0);
for (i = 0; i < ARR_SIZE; i++) {
arr[i] = rand() % 10 + 1;
}
// cout << "Array: ";
// for (i = 0; i < ARR_SIZE; i++)
// cout << arr[i] << " ";
// cout << std::endl;
#pragma omp parallel num_threads(4)
{
#pragma omp for
for(i = 0; i < ARR_SIZE; i += STEP_SIZE) {
int j, start = i, end = i + STEP_SIZE - 1;
#pragma omp critical
cout << "Computing Sum(" << start << ":" << end << ") from "
<< omp_get_thread_num() << " of " << omp_get_num_threads() << " threads." << endl;
#pragma omp task
{
int partial_sum = 0;
#pragma omp critical
cout << "Task Computing Sum(" << start << ":" << end << ") from "
<< omp_get_thread_num() << " of " << omp_get_num_threads() << " threads." << endl;
for(j = start; j <= end; j++)
partial_sum += arr[j];
#pragma omp atomic
sum += partial_sum;
}
}
}
#pragma omp critical
cout << "Sum of array is : " << sum << endl;
return 0;
}
quicksorttask
#include
#include
#include
#include <omp.h>
using namespace std;
#define SIZE 20
void quicksort(int arr[], int left, int right) {
if (left >= right) return;
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
std::swap(arr[++i], arr[j]);
}
}
std::swap(arr[i + 1], arr[right]);
int partitionIdx = i + 1;
#pragma omp task if(right - left > 100) // Only if segment is large enough
quicksort(arr, left, partitionIdx - 1);
#pragma omp task if(right - left > 100)
quicksort(arr, partitionIdx + 1, right);
}
int main() {
int arr[SIZE];
// Fill array with random numbers between 1 and 100
srand(time(0));
for (int i = 0; i < SIZE; i++) {
arr[i] = rand() % 100 + 1;
}
cout << "Unsorted array: ";
for (int i = 0; i < SIZE; i++)
cout << arr[i] << " ";
cout << endl;
#pragma omp parallel
{
#pragma omp single
quicksort(arr, 0, SIZE - 1);
}
cout << "Sorted array: ";
for (int i = 0; i < SIZE; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
qs using secrions
int main() {
int arr[SIZE];
// Fill array with random numbers between 1 and 100
srand(time(0));
for (int i = 0; i < SIZE; i++) {
arr[i] = rand() % 100 + 1;
}
// cout << "Unsorted array: ";
// for (int i = 0; i < SIZE; i++)
// cout << arr[i] << " ";
// cout << endl;
#pragma omp parallel
{
#pragma omp single
quicksort(arr, 0, SIZE - 1);
}
// cout << "Sorted array: ";
// for (int i = 0; i < SIZE; i++)
// cout << arr[i] << " ";
// cout << endl;
return 0;
}