Was ist das Gegenteil von „peinlich parallel“?

Question

Laut Wikipedia ein „peinlichen parallel“ Problem ist ein, für das wenig oder gar keine Anstrengung erforderlich ist, um das Problem in eine Reihe von parallelen Aufgaben zu trennen. Raytracing wird oft als Beispiel angeführt, weil jeder Strahl kann im Prinzip parallel verarbeitet werden.

Offensichtlich sind einige Probleme viel schwieriger zu parallelisieren. Einige können sogar unmöglich sein. Ich frage mich, was Begriffe verwenden, und was die Standardbeispiele sind für diese schwierigen Fälle.

Kann ich "Ärgerlicher Sequential" als mögliche Namen vor?

Answer 1

Inherently sequenzieller .

Beispiel: Die Zahl der Frauen wird nicht die Länge der Schwangerschaft verringern.

Answer 2

Es gibt mehr als ein Gegenteil eines „peinliche parallel“ -Problem.

Perfekt sequenzielle

Ein gegenüber ist ein Nicht-parallelizable Problem, das heißt, ein Problem, für das keine I / O-bound Probleme „, berechnen f ^1000000 (x ₀ )“Art der Probleme, die Berechnung bestimmter kryptographische Hash-Funktionen .

kommunikationsintensiven

Ein weiteres Gegenteil ist ein parallelizable Problem, das vielen parallelen Kommunikation erfordert (a kommunikationsintensiven Problem). Eine Implementierung eines solchen Problems wird auf einem Supercomputer mit hoher Bandbreite und geringer Latenz-Verbindung nur richtig skaliert werden. Vergleichen Sie dies mit embarrassingly parallel Problemen, Implementierungen von denen laufen effizient auch auf Systeme mit sehr schlechter Verbindung (zB Farmen ).

Bemerkenswerte Beispiel eines kommunikationsintensiven Problem: Lösung A x = b wo A eine große, dichte Matrix ist. Wie in der Tat, ist eine Implementierung des Problems verwendet, um das TOP500 Ranking zu kompilieren. Es ist ein guter Maßstab, wie sie betont sowohl die Rechenleistung des einzelnen CPUs und die Qualität der Verbindung (aufgrund Intensität der Kommunikation).

In praktischer Hinsicht kann jedes mathematische Modell, das ein System von partiellen Differentialgleichungen auf einem regelmäßigen Gitter löst unter Verwendung von diskreten Zeitschritt (man denke: Wettervorhersagen, in silico Crashtests) ist, parallelizable von Domain Zersetzung . Das heißt, jede CPU übernimmt einen Teil des Gitters, und am Ende eines jeden Zeitschritt werden die CPUs ihre Ergebnisse auf Bereichsgrenzen mit „Nachbar“ CPUs tauschen. Dieser Austausch macht diese Klasse von Problemen kommunikationsintensiven.

Answer 3

Im eine harte Zeit, dies nicht zu veröffentlichen ... weil ich weiß, es fügt nichts zur Diskussion .. aber für alle southpark_old Fans da draußen

"Superserien!"

Answer 4

"Hartnäckig serial"?

Answer 5

Das Gegenteil von embarassingly parallel ist Amdahl Gesetz , die besagt, dass einige Aufgaben nicht sein kann parallel, und dass die minimale Zeit erfordert eine vollkommen parallele Aufgabe durch den rein sequentiellen Teil dieser Aufgabe bestimmt wird.

Answer 6

"Standardbeispiele" sequenzieller Prozesse:

• ein Baby machen „Crash-Programme scheitern, weil sie auf der Theorie basiert, dass mit neun Frauen schwanger, Sie ein Baby im Monat bekommen können“ - zugeschrieben Werner von Braun
• Berechnung pi, e, sqrt (2) und andere irrationale Zahlen auf Millionen von Stellen: Die meisten Algorithmen sequenzielle
• Navigation: erhalten von Punkt A nach Punkt Z, müssen Sie zunächst durch einige Zwischenpunkte B gehen, C, D, usw.
.
• Newton-Methode: Sie müssen jede Annäherung, um die nächste, bessere Annäherung
berechnen
• Challenge-Response-Authentifizierung
• -Taste Stärkung
• Hash-Kette
• Hashcash

Answer 7

P-complete (aber das ist sicher noch nicht bekannt).

Answer 8

Ich verwende "erniedrigend Sequential"

Paul

Answer 9

"Gladdengly Sequential"

Answer 10

Das alles hat mit Datenabhängigkeiten zu tun. Peinlich parallel Probleme sind diejenigen, für die die Lösung aus vielen unabhängigen Teilen. Probleme mit dem anderen dieser Art würden diejenigen sein, die massiven Datenabhängigkeiten haben, wo es wenig bis gar nichts ist, die parallel ausgeführt werden können. degenerativ abhängig

Answer 11

Der Begriff, den ich gehört habe, werden am häufigsten „eng gekoppelt“, dass jeder Prozess in Wechselwirkung treten muß und kommuniziert oft, um Zwischendaten zu teilen. Grundsätzlich hängt jeder Prozess auf andere ihre Berechnung zu vervollständigen.

Zum Beispiel Matrix-Verarbeitung beinhaltet oft Randwerte an den Rand der einzelnen Array-Partition zu teilen.

Dies ist im Gegensatz zu embarassingly parallel (oder losen gekoppelten) Problemen, bei denen jeder Teil des Problems ist, vollständig in sich geschlossene, und keine (oder nur sehr wenig) IPC benötigt. Denken Sie Master / Arbeiter Parallelität.

Answer 12

prahlerisch sequentiell.

Answer 13

Ich habe immer bevorzugt 'traurig sequentielle'ala des Trennschrittes in quicksort.

Answer 14

Wenn überhaupt sollte man spekulieren, was es sein würde, natürlich, unverbesserlich sequenziellen Probleme zu haben, versuchen Sie

wohlig sequenzielle

entgegenzutreten ' embarrassingly parallel '.

Answer 15

"Completely Serien?"

Es sollte nicht wirklich überraschen, dass Wissenschaftler mehr darüber nachdenken, was kann getan werden, was nicht getan werden kann. Gerade in diesem Fall, wo die Alternative zur Parallelisierung ist alles so, wie man tut normalerweise tun würde.

Answer 16

Völlig nicht-parallelizable? Pessimally parallelizable?

Answer 17

Das Gegenteil ist der "disconcertingly Serie".

Answer 18

unter Berücksichtigung, dass die Parallelität ist die Handlung viele Arbeitsplätze in dem gleichen Zeitschritt t tun. das Gegenteil könnte zeitsequenzielle Probleme

Answer 19

Ein Beispiel von Natur aus sequenziellem Problem. Dies ist üblich in CAD-Paketen und einige Arten von Engineering-Analyse.

Baum-Traversal mit Datenabhängigkeiten zwischen den Knoten.

Stellen Sie sich eine grafische Darstellung durchqueren und addieren Gewichte von Knoten.

Sie können einfach parallelisieren es nicht.

CAD-Software stellt Teile wie ein Baum, und zu machen, um das Objekt, um den Baum zu durchlaufen haben. Aus diesem Grund verwenden CAD-Arbeitsplätze weniger Kerne und schneller, anstatt viele Kerne.

Danke für das Lesen.

Answer 20

Sie könnte natürlich, aber ich denke, dass beide Namen 'sind kein Thema. Aus funktionaler Programmierung Perspektive könnte man sagen, dass der ‚annoyingly sequenzielle‘ Teil der kleinste mehr oder weniger unabhängigen Teil eines Algorithmus ist.

Während die ‚peinliche parallel‘, wenn nicht in die Tat zu einem parallelen Ansatz ist schlecht Codierung Praxis.

So sehe ich keinen Punkt in der gegebenen diesen Dingen einen Namen, wenn eine gute Codierung der Praxis immer zu bremsen Sie Ihre Lösung in unabhängige Stücke ist, auch wenn man in diesem Moment nicht nutzen Parallelität.