Параллельный и однопоточный код, имеющий относительно одинаковую производительность в Java

Question

Я написал программу для визуализации Джулии Сет . Однопоточный код довольно прост и по сути таков:

private Image drawFractal() {
    BufferedImage img = new BufferedImage(WIDTH, HEIGHT, BufferedImage.TYPE_INT_ARGB);
    for (int x = 0; x < WIDTH; x++) {
        for (int y = 0; y < HEIGHT; y++) {
            double X = map(x,0,WIDTH,-2.0,2.0);
            double Y = map(y,0,HEIGHT,-1.0,1.0);
            int color = getPixelColor(X,Y);

            img.setRGB(x,y,color);
        }
    }

    return img;
}

private int getPixelColor(double x, double y) {
    float hue;
    float saturation = 1f;
    float brightness;

    ComplexNumber z = new ComplexNumber(x, y);
    int i;
    for (i = 0; i < maxiter; i++) {
        z.square();
        z.add(c);
        if (z.mod() > blowup) {
            break;
        }
    }

    brightness = (i < maxiter) ? 1f : 0;
    hue = (i%maxiter)/(float)maxiter;
    int rgb = Color.getHSBColor(hue,saturation,brightness).getRGB();
    return rgb;
}

Как видите, это крайне неэффективно. Таким образом, я пошел на распараллеливание этого кода, используя инфраструктуру fork / join в Java, и вот что я придумал:

private Image drawFractal() {
    BufferedImage img = new BufferedImage(WIDTH, HEIGHT, BufferedImage.TYPE_INT_ARGB);

    ForkCalculate fork = new ForkCalculate(img, 0, WIDTH, HEIGHT);
    ForkJoinPool forkPool = new ForkJoinPool();
    forkPool.invoke(fork);
    return img;
}

//ForkCalculate.java
public class ForkCalculate extends RecursiveAction {
BufferedImage img;
int minWidth;
int maxWidth;
int height;
int threshold;
int numPixels;

ForkCalculate(BufferedImage b, int minW, int maxW, int h) {
    img = b;
    minWidth = minW;
    maxWidth = maxW;
    height = h;
    threshold = 100000; //TODO : Experiment with this value.
    numPixels = (maxWidth - minWidth) * height;
}

void computeDirectly() {
    for (int x = minWidth; x < maxWidth; x++) {
        for (int y = 0; y < height; y++) {
            double X = map(x,0,Fractal.WIDTH,-2.0,2.0);
            double Y = map(y,0,Fractal.HEIGHT,-1.0,1.0);
            int color = getPixelColor(X,Y);

            img.setRGB(x,y,color);
        }
    }
}

@Override
protected void compute() {
    if(numPixels < threshold) {
        computeDirectly();
        return;
    }

    int split = (minWidth + maxWidth)/2;

    invokeAll(new ForkCalculate(img, minWidth, split, height), new ForkCalculate(img, split, maxWidth, height));
}

private int getPixelColor(double x, double y) {
    float hue;
    float saturation = 1f;
    float brightness;

    ComplexNumber z = new ComplexNumber(x, y);
    int i;
    for (i = 0; i < Fractal.maxiter; i++) {
        z.square();
        z.add(Fractal.c);
        if (z.mod() > Fractal.blowup) {
            break;
        }
    }

    brightness = (i < Fractal.maxiter) ? 1f : 0;
    hue = (i%Fractal.maxiter)/(float)Fractal.maxiter;
    int rgb = Color.getHSBColor(hue*5,saturation,brightness).getRGB();
    return rgb;

}

private double map(double x, double in_min, double in_max, double out_min, double out_max) {
    return (x-in_min)*(out_max-out_min)/(in_max-in_min) + out_min;

}
}

Я проверил с диапазоном значений, варьирующих maxiter , blowup и threshold .

Я сделал порог таким, чтобы количество потоков было примерно таким же, как количество ядер, которые у меня есть (4).

Я измерил время выполнения в обоих случаях и ожидал некоторой оптимизации в параллельном коде. Однако код выполнялся в одно и то же время, если не иногда Это сбило меня с толку. Это происходит потому, что размер проблемы недостаточно велик? Я также проверил с различными размерами изображения в диапазоне от 640 * 400 до 1020 * 720.

Почему это происходит? Как я могу запустить код параллельно, чтобы он работал быстрее, чем нужно?

Редактировать Если вы хотите полностью проверить код, перейдите на мой Github Основная ветвь имеет однопоточный код. Ветка с именем Multicore имеет код распараллеливания.

Редактировать 2 Изображение фрактала для справки.

Answer 1

Вот ваш код, переписанный для использования параллелизма. Я обнаружил, что в моем Lenovo Yoga число процессоров искажено вдвое. Кроме того, Windows 10, кажется, требует огромного количества обработки, поэтому результаты на моем ноутбуке сомнительны. Если у вас больше ядер или приличная ОС, она должна быть намного лучше.

package au.net.qlt.canvas.test;

import javax.swing.*;
import java.awt.*;
import java.awt.image.BufferedImage;

public class TestConcurrency extends JPanel {

    private BufferedImage screen;
    final Fractal fractal;

    private TestConcurrency(final Fractal f, Size size) {
        fractal = f;
        screen = new BufferedImage(size.width, size.height, BufferedImage.TYPE_INT_ARGB);
        setBackground(Color.BLACK);
        setPreferredSize(new Dimension(size.width,size.height));
    }

    public void test(boolean CONCURRENT) {
        int count = CONCURRENT ? Runtime.getRuntime().availableProcessors()/2 : 1;
        Scheduler scheduler = new Scheduler(fractal.size);
        Thread[] threads = new Thread[count];
        long startTime = System.currentTimeMillis();
        for (int p = 0; p < count; p++) {
            threads[p] = new Thread() {
                public void run() {
                    scheduler.schedule(fractal,screen);
                }
            };
            threads[p].start();
            try {
                threads[p].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        DEBUG("test threads: %d - elasped time: %dms", count, (System.currentTimeMillis()-startTime));
    }
    @Override public void paint(Graphics g)       {
        if(g==null) return;
        g.drawImage(screen, 0,0, null);
    }

    public static void main(String[]args) {
        JFrame frame = new JFrame("FRACTAL");
        Size size = new Size(1024, 768);
        Fractal fractal = new Fractal(size);
        TestConcurrency test = new TestConcurrency(fractal, size);

        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setResizable(false);
        frame.add(test);
        frame.pack();
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);

        for(int i=1; i<=10; i++) {
            DEBUG("--- Test %d ------------------", i);
            test.test(false);
            test.repaint();
            test.test(true);
            test.repaint();
        }
    }
    public static void DEBUG(String str, Object ... args)   { Also System.out.println(String.format(str, args)); }
}

class Fractal {

    ComplexNumber C;
    private int maxiter;
    private int blowup;
    private double real;
    private double imaginary;
    private static double xs = -2.0, xe = 2.0, ys = -1.0, ye = 1.0;
    public Size size;

    Fractal(Size sz){
        size = sz;
        real        =     -0.8;
        imaginary   =     0.156;
        C           =     new ComplexNumber(real, imaginary);
        maxiter     =     400;
        blowup      =     4;
    }

    public int getPixelColor(Ref ref) {
        float hue;
        float saturation = 1f;
        float brightness;
        double X = map(ref.x,0,size.width,xs,xe);
        double Y = map(ref.y,0,size.height,ys,ye);
        ComplexNumber Z = new ComplexNumber(X, Y);

        int i;
        for (i = 0; i < maxiter; i++) {
            Z.square();
            Z.add(C);
            if (Z.mod() > blowup) {
                break;
            }
        }

        brightness = (i < maxiter) ? 1f : 0;
        hue = (i%maxiter)/(float)maxiter;
        return Color.getHSBColor(hue*5,saturation,brightness).getRGB();

    }
    private double map(double n, double in_min, double in_max, double out_min, double out_max) {
        return (n-in_min)*(out_max-out_min)/(in_max-in_min) + out_min;

    }
}
class Size{
    int width, height, length;
    public Size(int w, int h) { width = w; height = h; length = h*w; }
}
class ComplexNumber {
    private double real;
    private double imaginary;

    ComplexNumber(double a, double b) {
        real = a;
        imaginary = b;
    }

    void square() {
        double new_real = Math.pow(real,2) - Math.pow(imaginary,2);
        double new_imaginary = 2*real*imaginary;
        this.real = new_real;
        this.imaginary = new_imaginary;
    }

    double mod() {
        return Math.sqrt(Math.pow(real,2) + Math.pow(imaginary,2));
    }

    void add(ComplexNumber c) {
        this.real += c.real;
        this.imaginary += c.imaginary;
    }
}
class Scheduler {
    private Size size;
    private int x, y, index;
    private final Object nextSync = 4;

    public Scheduler(Size sz) { size = sz; }
    /**
     * Update the ref object with next available coords,
     * return false if no more coords to be had (image is rendered)
     *
     * @param ref Ref object to be updated
     * @return false if end of image reached
    */
    public boolean next(Ref ref) {
        synchronized (nextSync) {
            // load passed in ref
            ref.x = x;
            ref.y = y;
            ref.index = index;
            if (++index > size.length) return false;    // end of the image
            // load local counters for next access
            if (++x >= size.width) {
                x = 0;
                y++;
            }
            return true;        // there are more pixels to be had
        }
    }
    public void schedule(Fractal fractal, BufferedImage screen) {
        for(Ref ref = new Ref(); next(ref);)
            screen.setRGB(ref.x, ref.y, fractal.getPixelColor(ref));
    }
}
class Ref {
    public int x, y, index;
    public Ref() {}
}