جافا:Parallelizing نوع سريع عبر خيوط المعالجة المتعددة

Question

انا تجريب parallelizing خوارزميات بلغة جافا.بدأت مع دمج النوع ، وشارك محاولة مني في هذا السؤال.بلدي المنقحة محاولة في البرمجية أدناه ، حيث أنا الآن في محاولة يوازي سريعة نوعا ما.

هل هناك أي أخطاء بدائية في تنفيذ متعددة الخيوط أو نهج هذه المشكلة ؟ إذا لا, لا أتوقع أكثر من 32% زيادة سرعة بين متتابعة و بشكل متوازي الخوارزمية على مبارزة النواة (انظر الأوقات في الأسفل)?

هنا هو خاصية تعدد الخوارزمية:

    public class ThreadedQuick extends Thread
    {
        final int MAX_THREADS = Runtime.getRuntime().availableProcessors();

        CountDownLatch doneSignal;
        static int num_threads = 1;

        int[] my_array;
        int start, end;

        public ThreadedQuick(CountDownLatch doneSignal, int[] array, int start, int end) {
            this.my_array = array;
            this.start = start;
            this.end = end;
            this.doneSignal = doneSignal;
        }

        public static void reset() {
            num_threads = 1;
        }

        public void run() {
            quicksort(my_array, start, end);
            doneSignal.countDown();
            num_threads--;
        }

        public void quicksort(int[] array, int start, int end) {
            int len = end-start+1;

            if (len <= 1)
                return;

            int pivot_index = medianOfThree(array, start, end);
            int pivotValue = array[pivot_index];

            swap(array, pivot_index, end);

            int storeIndex = start;
            for (int i = start; i < end; i++) {
               if (array[i] <= pivotValue) {
                   swap(array, i, storeIndex);
                   storeIndex++;
               }
            }

            swap(array, storeIndex, end);

            if (num_threads < MAX_THREADS) {
                num_threads++;

                CountDownLatch completionSignal = new CountDownLatch(1);

                new ThreadedQuick(completionSignal, array, start, storeIndex - 1).start();
                quicksort(array, storeIndex + 1, end);

                try {
                    completionSignal.await(1000, TimeUnit.SECONDS);
                } catch(Exception ex) {
                    ex.printStackTrace();
                }
            } else {
                quicksort(array, start, storeIndex - 1);
                quicksort(array, storeIndex + 1, end);
            }
        }
    }

هنا هو كيف أبدأ:

ThreadedQuick.reset();
CountDownLatch completionSignal = new CountDownLatch(1);
new ThreadedQuick(completionSignal, array, 0, array.length-1).start();
try {
    completionSignal.await(1000, TimeUnit.SECONDS);
} catch(Exception ex){
    ex.printStackTrace();
}

أنا اختبرت هذا على المصفوفات.نوع مماثل متتابعة سريعة خوارزمية الفرز.وهنا توقيت النتائج على intel duel-core كمبيوتر محمول من dell ، في ثواني:

العناصر:500,000, متتابعة:0.068592, الخيوط:0.046871, المصفوفات.نوع:0.079677

العناصر:1,000,000, متتابعة:0.14416, الخيوط:0.095492, المصفوفات.نوع:0.167155

العناصر:2,000,000, متتابعة:0.301666, الخيوط:0.205719, المصفوفات.نوع:0.350982

العناصر:4,000,000, متتابعة:0.623291, الخيوط:0.424119, المصفوفات.نوع:0.712698

العناصر:8,000,000, متتابعة:1.279374, الخيوط:0.859363, المصفوفات.نوع:1.487671

كل رقم فوق هو متوسط الوقت من 100 الاختبارات رمي 3 أدنى و 3 أعلى الحالات.اعتدت عشوائي.nextInt(عدد صحيح.MAX_VALUE) لتوليد مجموعة لكل اختبار ، الذي تم تهيئته مرة واحدة كل 10 اختبارات مع نفس البذور.كل اختبار يتكون من توقيت معين الخوارزمية مع النظام.nanoTime.أنا تقريب إلى ستة أرقام عشرية بعد المتوسط.و من الواضح أنني لم تحقق لمعرفة ما إذا كان كل نوع عملت.

كما ترون, هناك حوالي 32% زيادة في السرعة بين متسلسلة و مترابطة الحالات في كل مجموعة من الاختبارات.كما سألت أعلاه, لا نتوقع أكثر من ذلك ؟

Answer 1

مما يجعل numThreads الساكنة يمكن أن يسبب مشاكل, فمن المحتمل جدا أن كنت في نهاية المطاف مع أكثر من MAX_THREADS تشغيل في بعض نقطة.

ربما السبب كنت لا تحصل على كامل ضعف في الأداء هو نوع سريع لا يمكن أن يكون كاملا parallelised.علما بأن المكالمة الأولى إلى فرز سريع سوف تمر من خلال مجموعة كاملة في بداية الموضوع قبل أن يبدأ حقا بالتوازي.هناك أيضا النفقات العامة في parallelising خوارزمية في شكل سياق التحول و وضع انتقالات عند الزراعة إلى المواضيع منفصلة.

إلقاء نظرة على مفترق/الانضمام إطار هذه المشكلة ربما يصلح بدقة تماما هناك.

بضع نقاط على التنفيذ.تنفيذ Runnable بدلا من توسيع الموضوع.يمتد خيط ينبغي أن تستخدم فقط عند إنشاء بعض نسخة جديدة من موضوع الفصل.عندما كنت ترغب فقط في بعض الوظائف أن يكون بالتوازي كنت أفضل حالا مع Runnable.في حين iplementing على Runnable يمكنك أيضا تمديد فئة أخرى مما يمنحك المزيد من المرونة في التصميم OO.استخدام بركة موضوع أن يقتصر على عدد من المواضيع المتاحة لديك في النظام.أيضا لا تستخدم numThreads إلى اتخاذ قرار بشأن ما إذا كان شوكة خارج موضوع جديد أو لا.يمكنك حساب هذا مقدما.استخدام الحد الأدنى من حجم القسم الذي هو حجم إجمالي مجموعة مقسوما على عدد المعالجات المتوفرة.شيء من هذا القبيل:

public class ThreadedQuick implements Runnable {

    public static final int MAX_THREADS = Runtime.getRuntime().availableProcessors();
    static final ExecutorService executor = Executors.newFixedThreadPool(MAX_THREADS);

    final int[] my_array;
    final int start, end;

    private final int minParitionSize;

    public ThreadedQuick(int minParitionSize, int[] array, int start, int end) {
        this.minParitionSize = minParitionSize;
        this.my_array = array;
        this.start = start;
        this.end = end;
    }

    public void run() {
        quicksort(my_array, start, end);
    }

    public void quicksort(int[] array, int start, int end) {
        int len = end - start + 1;

        if (len <= 1)
            return;

        int pivot_index = medianOfThree(array, start, end);
        int pivotValue = array[pivot_index];

        swap(array, pivot_index, end);

        int storeIndex = start;
        for (int i = start; i < end; i++) {
            if (array[i] <= pivotValue) {
                swap(array, i, storeIndex);
                storeIndex++;
            }
        }

        swap(array, storeIndex, end);

        if (len > minParitionSize) {

            ThreadedQuick quick = new ThreadedQuick(minParitionSize, array, start, storeIndex - 1);
            Future<?> future = executor.submit(quick);
            quicksort(array, storeIndex + 1, end);

            try {
                future.get(1000, TimeUnit.SECONDS);
            } catch (Exception ex) {
                ex.printStackTrace();
            }
        } else {
            quicksort(array, start, storeIndex - 1);
            quicksort(array, storeIndex + 1, end);
        }
    }    
}

يمكنك تشغيلها عن طريق القيام:

ThreadedQuick quick = new ThreadedQuick(array / ThreadedQuick.MAX_THREADS, array, 0, array.length - 1);
quick.run();

يبدأ هذا النوع في نفس الموضوع الذي يتجنب لا لزوم لها موضوع هوب في البدء.

التحذير:غير متأكد أعلاه التنفيذ سوف يكون في الواقع أسرع كما لم قياسها ذلك.

Answer 2

هذا يستخدم مزيج من نوع سريع و نوع الدمج.

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class ParallelSortMain {
    public static void main(String... args) throws InterruptedException {
        Random rand = new Random();
        final int[] values = new int[100*1024*1024];
        for (int i = 0; i < values.length; i++)
            values[i] = rand.nextInt();

        int threads = Runtime.getRuntime().availableProcessors();
        ExecutorService es = Executors.newFixedThreadPool(threads);
        int blockSize = (values.length + threads - 1) / threads;
        for (int i = 0; i < values.length; i += blockSize) {
            final int min = i;
            final int max = Math.min(min + blockSize, values.length);
            es.submit(new Runnable() {
                @Override
                public void run() {
                    Arrays.sort(values, min, max);
                }
            });
        }
        es.shutdown();
        es.awaitTermination(10, TimeUnit.MINUTES);
        for (int blockSize2 = blockSize; blockSize2 < values.length / 2; blockSize2 *= 2) {
            for (int i = 0; i < values.length; i += blockSize2) {
                final int min = i;
                final int mid = Math.min(min + blockSize2, values.length);
                final int max = Math.min(min + blockSize2 * 2, values.length);
                mergeSort(values, min, mid, max);
            }
        }
    }

    private static boolean mergeSort(int[] values, int left, int mid, int end) {
        int[] results = new int[end - left];
        int l = left, r = mid, m = 0;
        for (; l < left && r < mid; m++) {
            int lv = values[l];
            int rv = values[r];
            if (lv < rv) {
                results[m] = lv;
                l++;
            } else {
                results[m] = rv;
                r++;
            }
        }
        while (l < mid)
            results[m++] = values[l++];
        while (r < end)
            results[m++] = values[r++];
        System.arraycopy(results, 0, values, left, results.length);
        return false;
    }
}

Answer 3

بعض التعليقات إذا لم تفهم التعليمات البرمجية الخاصة بك الحق:

1. أنا لا أرى قفل حول numthreads كائن على الرغم من أنه يمكن الوصول إليها من خلال مواضيع متعددة.ربما يجب عليك أن تجعل من AtomicInteger.

2. استخدام بركة موضوع وترتيب المهام ، أيمكالمة واحدة إلى فرز سريع ، إلى اتخاذ advantange من تجمع مؤشرات الترابط.استخدام العقود الآجلة.

الحالي الخاص بك طريقة تقسيم الأشياء كما كنت تفعل يمكن أن تترك أصغر شعبة بخيط شعبة أكبر من دون موضوع.وهذا هو القول, أنه لا أولوية أكبر القطاعات الخاصة بهم مع المواضيع.