PARALLEL
PROGRAMMING
PRACTICAL FILE
NAME: PURNIMA
COURSE: BSC (H) COMPUTER SCIENCE
ROLL NUMBER: CSC/22/3
EXAMINATION ROLL NUMBER:
22044570003
YEAR: III
SEMESTER: VI
PRACTICAL 1
QUESTION: IMPLEMENT MATRIX-MATRIX MULTIPLICATION IN PARALLEL USING OPENMP
INPUT
#include <iostream>
#include <omp.h>
using namespace std;
int main() {
int N;
cout << "Enter the size of matrices (N x N): ";
cin >> N;
int A[N][N], B[N][N], C[N][N];
cout << "Enter elements of Matrix A:" << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> A[i][j];
}
}
cout << "Enter elements of Matrix B:" << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> B[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
C[i][j] = 0;
}
}
double start_time = omp_get_wtime();
int num_threads_used = 0;
#pragma omp parallel
{
#pragma omp single
num_threads_used = omp_get_num_threads();
#pragma omp for collapse(2)
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
}
double end_time = omp_get_wtime();
cout << "Result Matrix C:" << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << C[i][j] << "\t";
}
cout << endl;
}
cout << "Number of threads used: " << num_threads_used << endl;
cout << "Time taken for multiplication: " << (end_time - start_time) << " seconds" << endl;
return 0;
}
OUTPUT
PRACTICAL 2
QUESTION: IMPLEMENT DISTRIBUTED HISTOGRAM SORTING IN PARALLEL USING OPENMP
INPUT
#include <iostream>
#include <omp.h>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N;
cout << "Enter the number of elements: ";
cin >> N;
vector<int> arr(N);
cout << "Enter elements of the array:" << endl;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int num_threads_used = 0;
int min_val = *min_element(arr.begin(), arr.end());
int max_val = *max_element(arr.begin(), arr.end());
int bin_count = max_val - min_val + 1;
vector<int> histogram(bin_count, 0);
double start_time = omp_get_wtime();
#pragma omp parallel
{
int num_threads = omp_get_num_threads();
#pragma omp single
num_threads_used = num_threads;
vector<int> private_histogram(bin_count, 0);
#pragma omp for
for (int i = 0; i < N; i++) {
int index = arr[i] - min_val;
private_histogram[index]++;
}
#pragma omp critical
for (int i = 0; i < bin_count; i++) {
histogram[i] += private_histogram[i];
}
}
vector<int> sorted_arr;
for (int i = 0; i < bin_count; i++) {
for (int j = 0; j < histogram[i]; j++) {
sorted_arr.push_back(i + min_val);
}
}
double end_time = omp_get_wtime();
cout << "Sorted Array:" << endl;
for (int i = 0; i < sorted_arr.size(); i++) {
cout << sorted_arr[i] << " ";
}
cout << endl;
cout << "Number of threads used: " << num_threads_used << endl;
cout << "Time taken for sorting: " << (end_time - start_time) << " seconds" << endl;
return 0;
}
OUTPUT
PRACTICAL 3
QUESTION: IMPLEMENT BREADTH FIRST SEARCH IN PARALLEL USING OPENMP
INPUT
#include <iostream>
#include <vector>
#include <queue>
#include <omp.h>
using namespace std;
int main() {
int V, E;
cout << "Enter number of vertices and edges: ";
cin >> V >> E;
vector<vector<int>> adj(V);
cout << "Enter edges (u v):" << endl;
for (int i = 0; i < E; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<bool> visited(V, false);
queue<int> q;
int start;
cout << "Enter starting vertex: ";
cin >> start;
double start_time = omp_get_wtime();
visited[start] = true;
q.push(start);
int num_threads_used = 0;
while (!q.empty()) {
int size = q.size();
vector<int> current_level;
for (int i = 0; i < size; i++) {
int node = q.front();
q.pop();
current_level.push_back(node);
cout << node << " ";
}
#pragma omp parallel
{
#pragma omp single
num_threads_used = omp_get_num_threads();
#pragma omp for
for (int i = 0; i < current_level.size(); i++) {
int node = current_level[i];
for (int j = 0; j < adj[node].size(); j++) {
int neighbor = adj[node][j];
bool expected = false;
if (!visited[neighbor]) {
#pragma omp critical
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
}
}
double end_time = omp_get_wtime();
cout << endl;
cout << "Number of threads used: " << num_threads_used << endl;
cout << "Time taken for BFS: " << (end_time - start_time) << " seconds" << endl;
return 0;
}
OUTPUT
PRACTICAL 4
QUESTION: IMPLEMENT DIJKSTRA’S ALGORITHM IN PARALLEL USING OPENMP
INPUT
#include <iostream>
#include <vector>
#include <omp.h>
using namespace std;
int main() {
int V, E;
cout << "Enter number of vertices and edges: ";
cin >> V >> E;
vector<vector<pair<int, int>>> adj(V);
cout << "Enter edges (u v w):" << endl;
for (int i = 0; i < E; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int src;
cout << "Enter source vertex: ";
cin >> src;
vector<int> dist(V, 1e9);
vector<bool> visited(V, false);
dist[src] = 0;
int num_threads_used = 0;
double start_time = omp_get_wtime();
for (int count = 0; count < V - 1; count++) {
int u = -1;
int min_dist = 1e9;
#pragma omp parallel
{
#pragma omp single
num_threads_used = omp_get_num_threads();
int local_min = 1e9, local_u = -1;
#pragma omp for nowait
for (int i = 0; i < V; i++) {
if (!visited[i] && dist[i] < local_min) {
local_min = dist[i];
local_u = i;
}
}
#pragma omp critical
{
if (local_min < min_dist) {
min_dist = local_min;
u = local_u;
}
}
}
if (u == -1) break;
visited[u] = true;
#pragma omp parallel for
for (int v = 0; v < V; v++) {
for (auto edge : adj[u]) {
if (edge.first == v && !visited[v] && dist[u] + edge.second < dist[v]) {
dist[v] = dist[u] + edge.second;
}
}
}
}
double end_time = omp_get_wtime();
cout << "Shortest distances from source vertex " << src << ":" << endl;
for (int i = 0; i < V; i++) {
if (dist[i] == 1e9) cout << "INF ";
else cout << dist[i] << " ";
}
cout << endl;
cout << "Number of threads used: " << num_threads_used << endl;
cout << "Time taken for Dijkstra's: " << (end_time - start_time) << " seconds" << endl;
return 0;
}
OUTPUT
