Оптимизация алгоритма - параллельные AsyncTasks или потоки?

Это реалистичный алгоритм, но в идеале вы должны иметь возможность использовать одинаковое количество рабочих потоков во всей программе. Для этого вам нужно использовать четное количество потоков, скажем, 8.

На Pass1 Thread1 обрабатывает изображения 1–50, Thread2 обрабатывает изображения 51–100 и т. д.

На Pass2 потоки Thread1 и Thread2 обрабатывают изображения 1–100. Thread1 обрабатывает изображения 1–25 и 50–75, Thread2 обрабатывает изображения 26–50 и изображения 76–100. Затем Thread1 обрабатывает изображения 1–25 и 76–100, а Thread2 обрабатывает изображения 26–75.

Проходы с 3 по 8 выполняются по той же схеме — два потока, назначенные двум обрабатываемым группам, разделяют группы между собой. Таким образом, вы держите все свои потоки занятыми. Однако для этого вам понадобится четное число потоков, чтобы упростить разделение групп.

Пример кода для 4 потоков

class ImageGroup {
    final int index1;
    final int index2;
}

class ImageComparer implements Runnable {
    final Image[] images;
    ImageGroup group1;
    ImageGroup group2;

    public ImageComparer(Image[] images, ImageGroup group1, ImageGroup group2) {
        ...
    }

    public void run() {
        if(group2 == null) { // Compare images within a single group
            for(int i = group1.index1; i < group1.index2; i++) {
                for(int j = i + 1; j < group1.inex2; j++) {
                    compare(images[i], images[j]);
                }
            }
        } else { // Compare images between two groups
            for(int i = group1.index1; i < group1.index2; i++) {
                for(int j = group2.index1; j < group2.index2; j++) {
                    compare(images[i], images[j]);
                }
            }
        }
    }
}

ExecutorService executor = new ThreadPoolExecutor(); // use a corePoolSize equal to the number of target threads
// for 4 threads we need 8 image groups
ImageGroup group1 = new ImageGroup(0, 50);
ImageGroup group2 = new ImageGroup(50, 100);
...
ImageGroup group8 = new ImageGroup(450, 500);

ImageComparer comparer1 = new ImageComparer(images, group1, null);
ImageComparer comparer2 = new ImageComparer(images, group3, null);
...
ImageComparer comparer4 = new ImageComparer(images, group7, null);

// submit comparers to executor service
Future future1 = executor.submit(comparer1);
Future future2 = executor.submit(comparer2);
Future future3 = executor.submit(comparer3);
Future future4 = executor.submit(comparer4);

// wait for threads to finish
future1.get();
future2.get();
future3.get();
future4.get();

comparer1 = new ImageComparer(images, group2, null);
...
comparer4 = new ImageComparer(images, group8, null);

// submit to executor, wait to finish

comparer1 = new ImageComparer(images, group1, group3);
...
comparer4 = new ImageComparer(images, group7, group6);

// submit to executor, wait to finish

comparer1 = new ImageComparer(images, group1, group4);
...
comparer4 = new ImageComparer(images, group7, group5);