PP

Tanishk26

May 4th, 2025

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C 7.63 KB | None | 0 0

raw download clone embed print report

// Histogram //
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#define SIZE 1000
#define MAX_VAL 2000
int main() {
int *data = malloc(SIZE * sizeof(int));
int histogram_parallel[MAX_VAL] = {0};
// Generate random data
for (int i = 0; i < SIZE; i++)
data[i] = rand() % MAX_VAL;
// Compute histogram in parallel
double start = omp_get_wtime();
#pragma omp parallel for
for (int i = 0; i < SIZE; i++) {
#pragma omp atomic
histogram_parallel[data[i]]++;
}
double end = omp_get_wtime();
printf("Parallel Execution Time: %f seconds\n", end - start);
// Create the sorted array based on the histogram
int *sorted_array = malloc(SIZE * sizeof(int));
int index = 0;
for (int i = 0; i < MAX_VAL; i++) {
for (int j = 0; j < histogram_parallel[i]; j++) {
sorted_array[index++] = i;
}
}
// Print the sorted array
printf("Sorted array:\n");
for (int i = 0; i < SIZE; i++) {
printf("%d ", sorted_array[i]);
}
printf("\n");
// Free allocated memory
free(data);
free(sorted_array);
return 0;
}
// BFS //
#include <stdio.h>
#include <stdbool.h>
#include <omp.h>
#define MAX_VERTICES 100
#define MAX_EDGES 200 // Maximum edges per vertex
typedef struct {
int V; // Number of vertices
int adj[MAX_VERTICES][MAX_EDGES]; // Adjacency lists
int adjSize[MAX_VERTICES]; // Size of each adjacency list
} Graph;
void initGraph(Graph* graph, int V) {
if (V > MAX_VERTICES) {
printf("Error: Exceeds maximum vertices (%d)\n", MAX_VERTICES);
return;
}
graph->V = V;
for (int i = 0; i < V; i++) {
graph->adjSize[i] = 0;
}
}
void addEdge(Graph* graph, int v, int w) {
if (v >= graph->V || w >= graph->V) {
printf("Error: Vertex index out of bounds\n");
return;
}
if (graph->adjSize[v] >= MAX_EDGES || graph->adjSize[w] >= MAX_EDGES) {
printf("Error: Maximum edges per vertex reached (%d)\n", MAX_EDGES);
return;
}
graph->adj[v][graph->adjSize[v]++] = w;
graph->adj[w][graph->adjSize[w]++] = v;
}
void addEdgesFromUser(Graph* graph) {
int numEdges;
printf("Enter number of edges: ");
scanf("%d", &numEdges);
printf("Enter edges as pairs of vertices (0-based indexing):\n");
for (int i = 0; i < numEdges; i++) {
int v, w;
scanf("%d %d", &v, &w);
addEdge(graph, v, w);
}
}
void parallelBFS(Graph* graph, int start) {
if (start >= graph->V) {
printf("Error: Start vertex out of bounds\n");
return;
}
bool visited[MAX_VERTICES] = {false};
int queue[MAX_VERTICES];
int front = 0, rear = 0;
visited[start] = true;
queue[rear++] = start;
printf("BFS Traversal starting from vertex %d:\n", start);
while (front < rear) {
int current = queue[front++];
printf("%d ", current);
#pragma omp parallel for
for (int i = 0; i < graph->adjSize[current]; i++) {
int neighbor = graph->adj[current][i];
// Atomic check if not visited
bool expected = false;
#pragma omp atomic capture
{ expected = visited[neighbor]; visited[neighbor] = true; }
if (!expected) {
#pragma omp critical
{
queue[rear++] = neighbor;
}
}
}
}
printf("\n");
}
int main() {
Graph g;
int vertexCount, startVertex;
printf("Enter number of vertices: ");
scanf("%d", &vertexCount);
initGraph(&g, vertexCount);
addEdgesFromUser(&g);
printf("Enter starting vertex for BFS: ");
scanf("%d", &startVertex);
parallelBFS(&g, startVertex);
return 0;
}
// Dijakstra //
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <omp.h>
#define V 10
int minDistance(int dist[], int sptSet[]) {
int min = INT_MAX, min_index = -1;
#pragma omp atomic
for (int v = 0; v < V; v++) {
if (!sptSet[v] && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}
void dijkstra(int graph[V][V], int src) {
int dist[V], sptSet[V];
#pragma omp parallel for
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = 0;
}
dist[src] = 0;
#pragma omp parallel for
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
if (u == -1) break;
sptSet[u] = 1;
for (int v = 0; v < V; v++) {
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// Uncomment to print the constructed distance array
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
printf("\n");
}
int main() {
int graph[V][V];
srand(0);
#pragma omp parallel for collapse(2)
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
graph[i][j] = (i == j) ? 0 : rand() % 11;
}
}
// double start_time = omp_get_wtime();
dijkstra(graph, 0);
// double end_time = omp_get_wtime();
// printf("Execution time: %f seconds\n", end_time - start_time);
return 0;
}
// Matrix Multiplication
#include <stdio.h>
#include <stdlib.h>
#include <omp.h> // Include OpenMP header
#define MAX 500
int A[MAX][MAX], B[MAX][MAX], C[MAX][MAX];
int r1, c1, r2, c2;
// Function to generate random elements for matrices using OpenMP
void generate_random_elements(int matrix[MAX][MAX], int rows, int cols) {
#pragma omp parallel for
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
matrix[i][j] = rand() % 100; // Random numbers between 0 and 99
}
}
}
int main() {
srand(42); // Seed for random number generation
printf("Enter rows and columns for matrix A: ");
scanf("%d%d", &r1, &c1);
printf("Enter rows and columns for matrix B: ");
scanf("%d%d", &r2, &c2);
if (c1 != r2) {
printf("Matrix multiplication not possible.\n");
return -1;
}
// Generate random elements for matrices A and B
printf("Generating random elements for matrix A...\n");
generate_random_elements(A, r1, c1);
printf("Generating random elements for matrix B...\n");
generate_random_elements(B, r2, c2);
// Measure the time taken for matrix multiplication
double start_time = omp_get_wtime();
// Parallelize the matrix multiplication using OpenMP
#pragma omp parallel for
for (int i = 0; i < r1; i++) {
for (int j = 0; j < c2; j++) {
C[i][j] = 0;
for (int k = 0; k < c1; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
double end_time = omp_get_wtime();
// Display the resultant matrix
printf("Resultant matrix C:\n");
for (int i = 0; i < r1; i++) {
for (int j = 0; j < c2; j++) {
printf("%d ", C[i][j]);
}
printf("\n");
}
// Display the time taken and the number of threads used
printf("Time taken for matrix multiplication: %f seconds\n", end_time - start_time);
printf("Number of threads used: %d\n", omp_get_max_threads());
return 0;
}

Add Comment

Please, Sign In to add comment