Algoritmo di ordinamento parallelo che confronta tutti gli elementi

Se la metrica di confronto è un valore booleano (come indicato nei commenti), allora ci sono due possibilità.

1. La metrica è transitiva (se comp(A, B) restituisce true e comp(B, C) restituisce true, quindi comp(A, C) deve anche restituire true). In questo caso, la metrica di confronto per due elementi casuali segue quasi banalmente da dove quegli elementi sono finiti nella sequenza ordinata. L'unica complicazione potrebbe provenire da elementi che dovrebbero essere considerati uguali.

2. La metrica è non transitiva (se comp(A, B) restituisce true e comp(B, C) restituisce true, quindi comp(A, C) non per definizione restituisce true). In questo caso, la metrica è effettivamente inadatta per l'ordinamento degli elementi, perché non definisce correttamente un ordine per gli elementi.

I'm implementing an algorithm that needs to [implement sort and comprehensive set comparison in parallel]

No, ciò che tu devi fare è implementarlo prima in serie , quindi scopri come tradurre questo in parallelo . Non si avvia il cancello con un algoritmo sviluppato in parallelo con il primo che ne crea uno che funzioni in serie.

Il motivo per cui non inizi in parallelo è per una lista molto ampia di motivi, ma ti fornirò alcuni dei più importanti in cima alla mia testa:

• Non sai se il tuo programma verrà effettivamente tradotto in parallelo a meno che tu non scriva il tuo programma in prima istanza

• Non sai se il tuo programma funzionerà meglio / qualsiasi parte che in realtà funzionerà meglio in parallelo con in realtà la scrittura del tuo programma in serie prima

• Non sarai in grado di testare bene il tuo programma senza avere un programma che funzioni effettivamente prima in serie

In generale ci sono troppe domande se in realtà non si implementa il programma in serie prima, quindi fallo, non saltare e assumere che tutto vada meglio in parallelo, probabilmente non lo farà.

(this will be done on a GPU, but that doesn't matter much)

Sì, sì sarà importante molto . Il parallelismo della CPU ha confini completamente diversi rispetto alla GPU parallela, i thread sono completamente indipendenti e non serializzeranno il tuo programma se un thread ha colpito un'istruzione divergente.

D'altra parte, in genere dovrai copiare i dati per la CPU per condividerlo se stai lavorando sulla stessa attività, e ram non può in realtà essere l'accesso in parallelo in DDRN per casi di grandi dimensioni, a differenza di GDDRN. E a differenza delle GPU non puoi supporre che le attività di O (N) che possono essere equamente suddivise siano attività O (N / N) e invece devi assumere O (N / (costante piccola)) (che, pur non essendo un assunto valido) su GPU, questo è il tipo di pensiero che devi avere durante l'elaborazione dei dati, poiché assomiglia più a O (N / 20.000)).

in breve, le operazioni parallele della CPU possono gestire molto bene le operazioni Multiple Instruction, Multiple Data (MIMD),

Le GPU gestiranno le attività SIMD (Single Instruction Multiple Data) molto bene.

Il tuo problema potrebbe preferire un'architettura rispetto all'altra o non funzionare / dare una velocità in uno rispetto all'altro (a causa del cambio di contesto sulla CPU o della serializzazione implicita in GPU).

My initial plan was to use bitonic sort for step 1 but I don't think bitonic sort compares every pair of elements. Also, first doing a bitonic sort and then computing the metric for every pair of elements seems a tad inefficient because ALL the comparisons computed during the bitonic sort would be repeated in the second step.

L'ordinamento bitonico ha una complessità di runtime seriale di O (n log ^ 2 (n)), questo è il numero di confronti che devono essere eseguiti, in parallelo, il tempo di esecuzione è O (log ^ 2 (n)), che è il numero di confronti effettuati per ciascun elemento.

Ora stai dicendo che hai richiesto tutti i confronti da fare . se la tua N è, diciamo 256, quindi per ogni elemento, avrai esattamente 64 confronti tra i tuoi 256 elementi che sono effettivamente confrontati .... Quindi non importa quale, solo 1/4 del tuo confronto può essere fatto con ordinamento bitonico, quindi se sei andato avanti con la testa e hai fatto il confronto con ogni elemento, avresti al massimo ottenuto un'efficienza del 25%, ma solo su quella parte dell'intero programma (sebbene il confronto per elemento sarebbe O (N) invece di O (log ^ 2 (n)) e O (N) > O (log ^ 2 (n)) di un lotto).

Potrebbe sembrare molto per te, ma ora lo spostamento fino a 4096. Ora stai facendo 12 ^ 2 = 144 confronti per ogni elemento ... su un totale 4096 necessario ...

Vuoi risparmiare ... il 3% sui confronti ... è davvero utile risparmiare così tanto? potresti persino renderlo più lento ...

Ma ora diamo un'occhiata al problema, pensaci per un secondo ... se hai bisogno di fare confronti N ^ 2 non importa cosa, perché hai bisogno che ogni coppia saggi confronti ... potresti anche ottenere sbarazzati del tipo bitonico interamente e trova la posizione di quell'elemento sommando i confronti con altri elementi, assumendo che tu abbia un meccanismo deterministico di rottura del legame nel tuo confronto.

EDIT: la tua metrica di confronto è in realtà la dominanza di un set, ma vuoi anche conservare l'ordine (l'ordinamento deve essere stabile in altre parole), quindi se stai facendo un ordinamento massimo, devi prendere in considerazione l'indice come bene di ogni elemento. Per questo motivo, dovrai modificare la metrica di confronto in un modo che non corrisponda effettivamente alla dominanza, come ordinamento bitonico non è stabile

Probabilmente dovrai includere anche un modo per codificare non dominato

class DominationEnum(Enum):
    DOMINATES = 1
    DOMINATED = 0
    NODOMINATION = -1


def foo(items)
    n = len(items);
    items_sorted= [null * n]
    items_dominance= [[false for j in range(n)] for i in range(n)]
    number_better_than = 0
    for i_index, i in enumerate(items):
        for j_index, j in enumerate(items):
            domination = is_dominant(i, j)
            items_dominance[i][j] = domination == DominationEnum.DOMINATES
            number_better_than += int(items_dominance[i][j]  or ((domination == DominationEnum.NODOMINATION) and (i_index < j_index))

        items_sorted[number_better_than] = i

Quanto sopra è il codice seriale per tale algoritmo, per renderlo parallelo rimuovere il ciclo esterno ed eseguirlo per istanza di thread.

#i_index is thread index
def foo(items, items_sorted, items_dominance, i_index)
    number_better_than = 0
    for j_index, j in enumerate(items):
            domination = is_dominant(i, j)
            items_dominance[i][j] = domination == DominationEnum.DOMINATES
            number_better_than += int(items_dominance[i][j]  or ((domination == DominationEnum.NODOMINATION) and (i_index < j_index)))

    items_sorted[number_better_than] = i

O modifica la metrica del confronto di ordinamento bitonico in

( i dominates j ) or (if neither i nor j dominates on another and index of i is before index of j) 

quindi esegui:

def foo(items, items_dominance, i_index)
    number_better_than = 0
    for j_index, j in enumerate(items):
         domination = is_dominant(i, j)
         items_dominance[i][j] = domination == DominationEnum.DOMINATES

Inoltre puoi dimezzare il numero di operazioni necessarie trovando la dominazione per [i][j] e usando quello per determinare quale sarebbe l'altro dominio (puoi capire se io domino j, è dominato, o non è dominato né domina j, che ti dà anche il risultato per [j][i] )