Parallel Algorithms এবং তাদের Efficiency গাইড ও নোট

Parallel Algorithms এমন অ্যালগরিদম যা একটি কাজ বা সমস্যা সমাধান করতে একাধিক প্রসেসর বা থ্রেড ব্যবহার করে। এর মাধ্যমে সমস্যার সমাধান দ্রুত এবং অধিক কার্যকরীভাবে করা যায়, বিশেষত যখন সমস্যার আকার বড় এবং জটিল হয়। সাধারণত Divide and Conquer ধরনের অ্যালগরিদমগুলিতে Parallel Processing খুব কার্যকরী হয়, যেখানে কাজকে ছোট ছোট অংশে ভাগ করা হয় এবং প্রতিটি অংশ একসাথে সমাধান করা হয়।

Java তে, Parallel Algorithms বাস্তবায়ন করার জন্য Java Concurrency API, Streams API, এবং ForkJoinPool এর মতো বিভিন্ন টুলস এবং লাইব্রেরি ব্যবহৃত হয়। এই টিউটোরিয়ালে, আমরা Parallel Algorithms এবং তাদের Efficiency নিয়ে আলোচনা করব, এবং কিভাবে Java তে এসব অ্যালগরিদম বাস্তবায়ন করা যায় তা দেখব।

1. Parallel Algorithms এর মৌলিক ধারণা

Parallel Algorithm এমন একটি অ্যালগরিদম যা একাধিক কাজ বা সাব-অপারেশন একযোগে (concurrently) সম্পন্ন করে। মূলত একাধিক প্রসেসর বা থ্রেড ব্যবহার করে একে অপরের সাথে সমন্বয় করে কাজ করা হয়। এর ফলে একক থ্রেডের তুলনায় সমস্যার সমাধান দ্রুত হয়।

Parallel Algorithms এর প্রধান উপকারিতা:

1. Performance Improvement: বড় সমস্যাগুলি দ্রুত সমাধান করা যায়।
2. Scalability: প্রসেসরের সংখ্যা বাড়ানোর সাথে সাথে অ্যালগরিদমের কার্যকারিতা উন্নত হয়।
3. Resource Utilization: কম্পিউটার সিস্টেমের সমস্ত রিসোর্স সঠিকভাবে ব্যবহার করা যায়।

2. Java তে Parallel Algorithms বাস্তবায়ন

Java তে Parallel Algorithms বাস্তবায়ন করতে বিভিন্ন পদ্ধতি রয়েছে:

• Multithreading: একাধিক থ্রেড ব্যবহার করে কাজ ভাগ করে দেওয়া।
• ForkJoinPool: এটি divide and conquer স্টাইলের কাজের জন্য ব্যবহৃত হয়, যেখানে বড় কাজ ছোট ছোট টাস্কে ভাগ করা হয়।
• Streams API: Streams API তে parallelStream() ব্যবহার করে সহজেই একাধিক থ্রেডে কাজ ভাগ করা যায়।

3. Parallel Sorting Algorithm (Merge Sort)

Merge Sort হল একটি divide and conquer অ্যালগরিদম যা O(n log n) সময় জটিলতায় কাজ করে। এই অ্যালগরিদমটিকে parallel করা হলে, বড় অ্যারে গুলো দ্রুত সজ্জিত করা যায়।

উদাহরণ: Parallel Merge Sort in Java

import java.util.Arrays;
import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinPool;

public class ParallelMergeSort {

    public static void mergeSort(int[] arr) {
        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new MergeSortTask(arr, 0, arr.length - 1));
    }

    // Recursive task to perform merge sort
    static class MergeSortTask extends RecursiveTask<Void> {
        int[] arr;
        int left, right;

        MergeSortTask(int[] arr, int left, int right) {
            this.arr = arr;
            this.left = left;
            this.right = right;
        }

        @Override
        protected Void compute() {
            if (left < right) {
                int mid = (left + right) / 2;

                // Split the task into two subtasks
                MergeSortTask leftTask = new MergeSortTask(arr, left, mid);
                MergeSortTask rightTask = new MergeSortTask(arr, mid + 1, right);

                // Fork the tasks
                leftTask.fork();
                rightTask.fork();

                // Wait for the subtasks to complete
                leftTask.join();
                rightTask.join();

                // Merge the sorted halves
                merge(arr, left, mid, right);
            }
            return null;
        }

        // Merging two halves
        private void merge(int[] arr, int left, int mid, int right) {
            int[] temp = new int[right - left + 1];
            int i = left, j = mid + 1, k = 0;

            while (i <= mid && j <= right) {
                if (arr[i] <= arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            }

            while (i <= mid) {
                temp[k++] = arr[i++];
            }

            while (j <= right) {
                temp[k++] = arr[j++];
            }

            System.arraycopy(temp, 0, arr, left, temp.length);
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 3, 7, 1, 6, 4, 8, 2, 5};
        System.out.println("Original Array: " + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

ব্যাখ্যা:

1. MergeSortTask: এটি একটি RecursiveTask যা ForkJoinPool এর মাধ্যমে কাজের ভাগ করে দেয়।
2. ForkJoinPool: এটি একটি পুল যা কাজের বিভাজন এবং সমন্বয় করে, এবং মুলত ছোট ছোট টাস্কগুলোকে সমান্তরালভাবে সম্পন্ন করতে সহায়তা করে।

আউটপুট:

Original Array: [9, 3, 7, 1, 6, 4, 8, 2, 5]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]

4. Parallel Searching Algorithm (Binary Search)

Binary Search হল একটি সাধারণ অনুসন্ধান অ্যালগরিদম যা O(log n) সময় জটিলতায় কাজ করে, তবে এটি শুধুমাত্র সাজানো অ্যারের জন্য কার্যকরী। যখন parallel করা হয়, তখন একাধিক থ্রেড ব্যবহার করে বিভিন্ন অংশে দ্রুত অনুসন্ধান করা যায়।

উদাহরণ: Parallel Binary Search in Java

import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinPool;

public class ParallelBinarySearch {

    public static int binarySearch(int[] arr, int key) {
        ForkJoinPool pool = new ForkJoinPool();
        return pool.invoke(new BinarySearchTask(arr, 0, arr.length - 1, key));
    }

    static class BinarySearchTask extends RecursiveTask<Integer> {
        int[] arr;
        int left, right, key;

        BinarySearchTask(int[] arr, int left, int right, int key) {
            this.arr = arr;
            this.left = left;
            this.right = right;
            this.key = key;
        }

        @Override
        protected Integer compute() {
            if (left <= right) {
                int mid = left + (right - left) / 2;

                if (arr[mid] == key) {
                    return mid;  // Key found
                }

                if (arr[mid] > key) {
                    return new BinarySearchTask(arr, left, mid - 1, key).fork().join();  // Search left
                } else {
                    return new BinarySearchTask(arr, mid + 1, right, key).fork().join();  // Search right
                }
            }
            return -1;  // Key not found
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17};
        int key = 7;
        int index = binarySearch(arr, key);
        if (index != -1) {
            System.out.println("Element found at index: " + index);
        } else {
            System.out.println("Element not found");
        }
    }
}

ব্যাখ্যা:

1. BinarySearchTask: এটি একটি RecursiveTask যা ইনপুট অ্যারে এবং কী-এর জন্য দুইটি সাব-অপারেশন ভাগ করে দেয় এবং fork এবং join মেথড ব্যবহার করে একে একে দুই অংশে অনুসন্ধান করে।
2. ForkJoinPool: এটি parallel প্রক্রিয়াগুলিকে সমন্বয় করে এবং সকল সাব-অপারেশন সমাপ্ত হওয়া পর্যন্ত অপেক্ষা করে।

আউটপুট:

Element found at index: 3

5. Parallel Algorithms এর Efficiency

Parallel Algorithms এর Efficiency অনেকাংশে নির্ভর করে:

1. Number of Processors: যদি প্রসেসরের সংখ্যা বেশি থাকে, তবে কাজ আরও দ্রুত সমাধান হতে পারে। তবে এর সাথে সিস্টেমের সীমাবদ্ধতা এবং কনটেক্সট সুইচিংয়ের সময় বৃদ্ধি পায়।
2. Overhead: ছোট ছোট টাস্কগুলোর মধ্যে সমন্বয় এবং পারস্পরিক যোগাযোগের খরচ বেড়ে যায়, যা কার্যকারিতা কমিয়ে দিতে পারে।
3. Task Division: কাজের সঠিকভাবে ভাগ করা হলে, কাজের সময় কমে যায় এবং কার্যকারিতা বৃদ্ধি পায়।

Parallel Algorithm Efficiency (General Case):

• Speedup: ব্যবহারিক ভাবে, speedup নির্ভর করে কাজের ভাগের প্রক্রিয়া এবং প্রসেসরের সংখ্যা (Amdahl's Law)।
• Scalability: সিস্টেমে আরও প্রসেসর যোগ করলে কর্মক্ষমতা কতটা বাড়ে সেটি scalability নির্দেশ করে।