Qual è l'opposto di & # 8220; imbarazzantemente parallelo & # 8221 ;?

Question

Secondo Wikipedia, un "imbarazzante parallelamente parallelo" il problema è uno per il quale è necessario uno sforzo minimo o nullo per separare il problema in una serie di attività parallele. Il raytracing è spesso citato come esempio perché ogni raggio può, in linea di principio, essere elaborato in parallelo.

Ovviamente, alcuni problemi sono molto più difficili da parallelizzare. Alcuni potrebbero anche essere impossibili. Mi chiedo quali termini vengano utilizzati e quali siano gli esempi standard per questi casi più difficili.

Posso proporre " fastidiosamente sequenziale " come nome possibile?

Answer 1

Inerentemente sequenziale .

Esempio: il numero di donne non riduce la durata della gravidanza.

Answer 2

C'è più di un contrario di un "imbarazzantemente parallelo" problema.

Perfettamente sequenziale

Un contrario è un problema non parallelizzabile , cioè un problema per il quale no speedup può essere raggiunto utilizzando più di un processore. Sono già stati pubblicati diversi suggerimenti, ma proporrei un altro nome: un problema perfettamente sequenziale .

Esempi: I / O-bound , " calcola f ^1000000 (x ₀ ) " tipo di problemi, calcolando alcune funzioni hash crittografiche .

intensive di comunicazione-

Un altro contrario è un problema parallelizzabile che richiede molte comunicazioni parallele (un problema ad alta intensità di comunicazione ). Un'implementazione di tale problema si ridimensionerà correttamente solo su un supercomputer con interconnessione a larghezza di banda elevata e bassa latenza. In contrasto con problemi imbarazzanti paralleli, le cui implementazioni funzionano in modo efficiente anche su sistemi con interconnessione molto scarsa (ad es. farms ).

Notevole esempio di problema ad alta intensità di comunicazione: risoluzione di A x = b dove A è una matrice ampia e densa. È un dato di fatto, un'implementazione del problema viene utilizzata per compilare la classifica TOP500 . È un buon punto di riferimento, poiché sottolinea sia la potenza computazionale delle singole CPU che la qualità dell'interconnessione (dovuta all'intensità della comunicazione).

In termini più pratici, qualsiasi modello matematico che risolva un sistema di equazioni differenziali parziali su una griglia regolare usando un passo temporale discreto (pensate: previsioni del tempo, in silico crash test), è parallelizzabile da decomposizione del dominio . Ciò significa che ogni CPU si occupa di una parte della griglia e alla fine di ogni passaggio le CPU scambiano i loro risultati sui confini della regione con "vicino". CPU. Questi scambi rendono questa classe di problemi ad alta intensità di comunicazione.

Answer 3

Sto facendo fatica a non pubblicare questo ... perché so che non aggiunge nulla alla discussione .. ma per tutti i fan di Southpark là fuori

" Super seriale! "

Answer 4

" Testardamente seriale " ;?

Answer 5

Il contrario di un parallelo imbarazzante è Legge di Amdahl , che afferma che alcuni compiti non possono essere parallelo e che il tempo minimo richiesto da un'attività perfettamente parallela è dettato dalla porzione puramente sequenziale di tale attività.

Answer 6

"esempi standard" dei processi sequenziali:

• fare un bambino: "I programmi di crash falliscono perché si basano sulla teoria secondo cui, con nove donne in gravidanza, puoi avere un bambino al mese". - Attribuito a Werner von Braun
• calcolo di pi, e, sqrt (2) e altri numeri irrazionali in milioni di cifre: la maggior parte degli algoritmi sequenziali
• navigazione: per passare dal punto A al punto Z, devi prima passare attraverso alcuni punti intermedi B, C, D, ecc.
• Metodo di Newton: è necessaria ciascuna approssimazione per calcolare la prossima approssimazione migliore
• autenticazione challenge-response
• rafforzamento delle chiavi
• catena hash
• Hashcash

Answer 7

P-complete (ma questo non è ancora noto per certo).

Answer 8

Uso " Humiliatedly Sequential "

Paul

Answer 9

" Gladdengly Sequential "

Answer 10

Tutto ha a che fare con le dipendenze dei dati. Problemi imbarazzanti paralleli sono quelli per cui la soluzione è composta da molte parti indipendenti. Problemi con l'opposto di questa natura sarebbero quelli che hanno enormi dipendenze di dati, dove c'è poco o niente che può essere fatto in parallelo. Degenerativamente dipendente ?

Answer 11

Il termine che ho sentito più spesso è "strettamente accoppiato", in quanto ogni processo deve interagire e comunicare spesso per condividere dati intermedi. Fondamentalmente, ogni processo dipende dagli altri per completare il loro calcolo.

Ad esempio, l'elaborazione della matrice comporta spesso la condivisione di valori limite ai bordi di ciascuna partizione di array.

Ciò è in contrasto con problemi imbarazzantimente paralleli (o vagamente accoppiati) in cui ogni parte del problema è completamente autonoma e non è necessario (o molto poco) IPC. Pensa al parallelismo maestro / lavoratore.

Answer 12

Incredibilmente sequenziale.

Answer 13

Ho sempre preferito "tristemente sequenziale" al passaggio della partizione in quicksort.

Answer 14

Se mai uno dovrebbe speculare su come sarebbe avere problemi sequenziali naturali, incorreggibili, prova

beatamente sequenziale

per contrastare ' imbarazzantemente parallelo '.

Answer 15

" Completamente seriale? "

Non dovrebbe davvero sorprenderti che gli scienziati pensino più a ciò che si può fare che a ciò che non si può fare. Soprattutto in questo caso, dove l'alternativa al parallelismo è fare tutto come si farebbe normalmente.

Answer 16

Completamente non parallelizzabile? Parallelamente pessimizzabile?

Answer 17

L'opposto è "sconcertantemente seriale".

Answer 18

tenendo conto che il parallelismo è l'atto di fare molti lavori nello stesso tempo passo t. l'opposto potrebbe essere problemi sequenziali nel tempo

Answer 19

Un problema intrinsecamente sequenziale di esempio. Questo è comune nei pacchetti CAD e in alcuni tipi di analisi ingegneristiche.

Attraversamento di alberi con dipendenze dei dati tra nodi.

Immagina di attraversare un grafico e di sommare pesi di nodi.

Non puoi parallelizzarlo.

Il software CAD rappresenta le parti come un albero e per renderizzare l'oggetto devi attraversare l'albero. Per questo motivo, le workstation cad usano meno core e più velocemente, piuttosto che molti core.

Grazie per aver letto.

Answer 20

Potresti ovviamente, comunque penso che entrambi i "nomi" non siano un problema. Dal punto di vista della programmazione funzionale si potrebbe dire che la parte 'fastidiosamente sequenziale' è la più piccola parte più o meno indipendente di un algoritmo.

Mentre il 'imbarazzante parallelismo', se non addirittura l'approccio parallelo, è una cattiva pratica di codifica.

Quindi non vedo un punto nel dare a queste cose un nome se la buona pratica di codifica è sempre quella di frenare la tua soluzione in pezzi indipendenti, anche se in quel momento non approfitti del parallelismo.