| http://dbpedia.org/ontology/abstract
|
In computer science, a parallel algorithm, … In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can do multiple operations in a given time. It has been a tradition of computer science to describe serial algorithms in abstract machine models, often the one known as random-access machine. Similarly, many computer science researchers have used a so-called parallel random-access machine (PRAM) as a parallel abstract machine (shared-memory). Many parallel algorithms are executed concurrently – though in general concurrent algorithms are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "sequential algorithms", by contrast with concurrent algorithms.", by contrast with concurrent algorithms.
, Ein paralleler Algorithmus ist ein Algorit … Ein paralleler Algorithmus ist ein Algorithmus, welcher zum Beispiel ein Problem der Komplexitätsklasse NC (Nick’s Class nach Nick Pippenger) in polynomieller Zeit lösen bzw. entscheiden kann. Jeder parallele Algorithmus kann auch sequentiell abgearbeitet werden. Umgekehrt sind auch viele bekannte sequentielle Algorithmen parallelisierbar, so z. B. einige bekannte Sortieralgorithmen wie Bubblesort oder Quicksort. Es gehört jedoch zu den offenen Fragen der theoretischen Informatik, ob alle Algorithmen, welche Probleme der Klassen P oder NP entscheiden, auch parallelisierbar sind. Für viele dieser Algorithmen wurde noch kein entsprechender paralleler Algorithmus gefunden, so dass die meisten Forscher heute davon ausgehen, dass dieses nicht der Fall ist. Zur Untersuchung paralleler Algorithmen verwendet man in der Regel ein spezielles Maschinenmodell, das von der Registermaschine abgeleitet ist, die Parallel Random Access Machine (PRAM).die Parallel Random Access Machine (PRAM).
, В информатике параллельный алгоритм, проти … В информатике параллельный алгоритм, противопоставляемый традиционным последовательным алгоритмам, — алгоритм, который может быть реализован по частям на множестве различных вычислительных устройств с последующим объединением полученных результатов и получением корректного результата. Некоторые алгоритмы достаточно просто поддаются разбиению на независимо выполняемые фрагменты. Например, распределение работы по проверке всех чисел от 1 до 100000 на предмет того, какие из них являются простыми, может быть выполнено путём назначения каждому доступному процессору некоторого подмножества чисел с последующим объединением полученных множеств простых чисел (похожим образом реализован, например, проект GIMPS). С другой стороны, большинство известных алгоритмов вычисления значения числа пи не допускают разбиения на параллельно выполняемые части, так как требуют результата предыдущей итерации выполнения алгоритма. Итеративные численные методы, такие как, например, метод Ньютона или задача трёх тел, также являются сугубо последовательными алгоритмами. Некоторые примеры рекурсивных алгоритмов достаточно сложно поддаются распараллеливанию. Одним из примеров является поиск в глубину на графах. Параллельные алгоритмы весьма важны ввиду постоянного совершенствования многопроцессорных систем и увеличения числа ядер в современных процессорах. Обычно проще сконструировать компьютер с одним быстрым процессором, чем с множеством медленных процессоров (при условии достижения одинаковой производительности). Однако производительность процессоров увеличивается главным образом за счёт совершенствования техпроцесса (уменьшения норм производства), чему мешают физические ограничения на размер элементов микросхем и тепловыделение. Указанные ограничения могут быть преодолены путём перехода к многопроцессорной обработке, что оказывается эффективным даже для малых вычислительных систем. Сложность последовательных алгоритмов выражается в объёме используемой памяти и времени (числе тактов процессора), необходимых для выполнения алгоритма. Параллельные алгоритмы требуют учёта использования ещё одного ресурса: подсистемы связей между различными процессорами. Существует два способа обмена между процессорами: использование общей памяти и системы передачи сообщений. Системы с общей памятью требуют введения дополнительных блокировок для обрабатываемых данных, налагая определённые ограничения при использовании дополнительных процессоров. Системы передачи сообщений используют понятия каналов и блоков сообщений, что создаёт дополнительный трафик на шине и требует дополнительных затрат памяти для организации очередей сообщений. В дизайне современных процессоров могут быть предусмотрены специальные коммутаторы (кроссбары) с целью уменьшения влияния обмена сообщениями на время выполнения задачи. Ещё одной проблемой, связанной с использованием параллельных алгоритмов, является балансировка нагрузки. Например, поиск простых чисел в диапазоне от 1 до 100000 легко распределить между имеющимися процессорами, однако некоторые процессоры могут получить больший объём работы, в то время как другие закончат обработку раньше и будут простаивать. Проблемы балансировки нагрузки ещё больше усугубляется при использовании гетерогенных вычислительных сред, в которых вычислительные элементы существенно отличаются по производительности и доступности (например, в грид-системах). Разновидность параллельных алгоритмов, называемая распределёнными алгоритмами, специально разрабатываются для применения на кластерах и в распределённых вычислительных системах с учётом ряда особенностей подобной обработки.ётом ряда особенностей подобной обработки.
, 並列アルゴリズム（へいれつアルゴリズム、英語: parallel algorithm）とは、アルゴリズムの各部分を異なる複数の処理装置（プロセッサ）上で実行し、最終的にそれらの結果を集めることで答えを得るアルゴリズム。
, En las ciencias de la computación, un algo … En las ciencias de la computación, un algoritmo paralelo, en oposición a los algoritmos clásicos o , es un algoritmo que puede ser ejecutado por partes en el mismo instante de tiempo por varias unidades de procesamiento, para finalmente unir todas las partes y obtener el resultado correcto. Algunos algoritmos son fácilmente divisibles en partes; como por ejemplo, un algoritmo que calcule todos los números primos entre 1 y 100, donde se podría dividir los números originales en subconjuntos y calcular los primos para cada uno de los subconjuntos de los números originales; al final, uniríamos todos los resultados y tendríamos la solución final del algoritmo. Otro ejemplo, puede ser el . Por el contrario, a veces los problemas no son tan fácilmente paralelizables, de ahí que estos problemas se conozcan como . Como ejemplo de estos métodos tendríamos los métodos numéricos iterativos como el método de Newton o el problema de los tres cuerpos. Por otro lado, algunos problemas son difícilmente paralelizables, aunque tengan una estructura recursiva. Como ejemplo de esto último tendríamos la en un grafo. Los algoritmos paralelos son importantes porque es más rápido tratar grandes tareas de computación mediante la paralelización que mediante técnicas secuenciales. Esta es la forma en que se trabaja en el desarrollo de los procesadores modernos, ya que es más difícil incrementar la capacidad de procesamiento con un único procesador que aumentar su capacidad de cómputo mediante la inclusión de unidades en paralelo, logrando así la ejecución de varios flujos de instrucciones dentro del procesador. Pero hay que ser cauto con la excesiva paralelización de los algoritmos ya que cada algoritmo paralelo tiene una parte secuencial y debido a esto, los algoritmos paralelos puedes llegar a un punto de saturación (ver Ley de Amdahl). Por todo esto, a partir de cierto nivel de paralelismo, añadir más unidades de procesamiento puede sólo incrementar el coste y la disipación de calor. El coste o complejidad de los algoritmos secuenciales se estima en términos del espacio (memoria) y tiempo (ciclos de procesador) que requiera. Los algoritmos paralelos también necesitan optimizar la comunicación entre diferentes unidades de procesamiento. Esto se consigue mediante la aplicación de dos paradigmas de programación y diseño de procesadores distintos: memoria compartida o paso de mensajes. La técnica memoria compartida necesita del uso de cerrojos en los datos para impedir que se modifique simultáneamente por dos procesadores, por lo que se produce un coste extra en ciclos de CPU desperdiciados y ciclos de bus. También obliga a serializar alguna parte del algoritmo. La técnica paso de mensajes usa canales y mensajes pero esta comunicación añade un coste al bus, memoria adicional para las colas y los mensajes y latencia en el mensaje. Los diseñadores de procesadores paralelos usan buses especiales para que el coste de la comunicación sea pequeño pero siendo el algoritmo paralelo el que decide el volumen del tráfico. Finalmente, una subclase de los algoritmos paralelos, los son algoritmos diseñados para trabajar en entornos tipo clusters y de computación distribuida, donde se usan otras técnicas, fuera del alcance de los algoritmos paralelos clásicos.ance de los algoritmos paralelos clásicos.
, Парале́льний алгори́тм в інформатиці (тако … Парале́льний алгори́тм в інформатиці (також конкурентний алгоритм), на відміну від традиційного послідовного, це алгоритм, який одночасно може виконуватися на багатьох обчислювальних приладах, з наступним об'єднанням отриманих результатів для отримання вірного загального результату. Деякі алгоритми легко піддаються розбиттю на подібні частини. Наприклад, розбиття роботи з перевірки всіх чисел від одного до ста тисяч на простоту може бути зроблено шляхом призначення кожному доступному процесору певної підмножини чисел, з наступним об'єднанням отриманих результатів в один список (схожим чином реалізовано, наприклад, проект GIMPS). З іншого боку, більшість відомих алгоритмів обчислення значення числа пі не дозволяє розбиття на частини, що виконуються окремо, через те, що для кожної ітерації алгоритму потрібен результат попередньої. Ітеративні чисельні методи, такі як метод Ньютона або задача трьох тіл, також є алгоритмами, яким властива послідовність. Деякі приклади рекурсивних алгоритмів досить складно піддаються одночасному виконанню. Одним з таких прикладів є пошук в глибину на графах. Паралельні алгоритми досить важливі з огляду на постійне вдосконалення багатопроцесорних систем і збільшення числа ядер у сучасних процесорах. Зазвичай простіше сконструювати комп'ютер з одним швидким процесором, ніж з багатьма повільними з тією ж продуктивністю. Однак збільшення продуктивності за рахунок вдосконалення одного процесора натрапляє на фізичні обмеження, такі як досягнення максимальної щільності елементів та тепловиділення. Зазначені обмеження можна подолати лише шляхом переходу до багатопроцесорної архітектури, що виявляється ефективним навіть у малих обчислювальних системах. Складність послідовних алгоритмів виявляється в обсязі використаної пам'яті та часу (число тактів процесора), необхідних для виконання алгоритму. Паралельні алгоритми вимагають використання ще одного ресурсу: підсистеми зв'язків між різними процесорами. Існує два способи обміну даними між процесорами: використання спільної пам'яті та система передачі повідомлень. Системи зі спільною пам'яттю вимагають введення додаткових блокувань для даних, що обробляються, і накладають певні обмеження під час використання додаткових процесорів. Системи передачі повідомлень використовують поняття каналів і блоків повідомлень, що створює додатковий трафік на шині та вимагає додаткових витрат пам'яті для організації черги повідомлень. У проектуванні сучасних процесорів використовують особливі шини схожі на поперечини , що робить витрати на зв'язок малими і надає змогу програмісту самому вирішувати наскільки великий обмін даними у паралельному алгоритмі потрібен. Ще однією проблемою використання паралельних алгоритмів є балансування навантаження. Наприклад, пошук простих чисел в діапазоні від одного до мільйона легко розподілити між наявними процесорами, однак деякі з них можуть отримати менший обсяг роботи і будуть простоювати. Балансування навантаження становить проблему, яка може бути предметом окремих досліджень. У гетерогенних обчислювальних середовищах, де обчислювальні елементи істотно відрізняються за продуктивністю і доступністю (наприклад, у грід-системах) вона набуває особливої важливості. Різновид паралельних алгоритмів під назвою розподілені алгоритми окремо розроблявся з метою застосування на кластерах і в середовищах розподілених обчислень з урахуванням властивостей подібної обробки.урахуванням властивостей подібної обробки.
, Algorytm równoległy - algorytm, który w da … Algorytm równoległy - algorytm, który w danej chwili pozwala na wykonywanie wielu operacji. Równoległe algorytmy są cenne ze względu na możliwość szybszego (w stosunku do jednego procesora) obliczania różnego typu zagadnień. Przy aktualnym stanie rozwoju procesorów dużo łatwiejsze jest połączenie wielu słabszych procesorów od stworzenia nowego o podobnej mocy obliczeniowej. Koszt algorytmów obliczany jest na podstawie wykonanej pracy (ilości cykli wszystkich procesorów), czasu działania i pamięci potrzebnej do działania. W odpowiednich modelach rozważane są także problemy jednoczesnego odczytu czy zapisu do pamięci wspólnej. Większość dostępnych algorytmów obliczających liczbę pi (π) nie mają możliwości zbyt łatwego podziału obliczeń na równoległe porcje danych. Wymagają one wyników z poprzedzającego kroku do faktycznego kontynuowania obliczeń w następnym kroku. Problemy takie nazywane są właściwie szeregowymi. Iteracyjne analizy numeryczne, takie jak Metoda Newtona czy problem trzech ciał, są również algorytmami szeregowymi. Niektóre z nich są bardzo trudne do zrównoleglenia, aczkolwiek są one rekurencyjne. Jednym z przykładów jest algorytm przeszukiwania w głąb dla grafów. Algorytmy równoległe są wartościowe, z uwagi na wprowadzenie znaczących ulepszeń w systemach wieloprocesorowych oraz postęp w dziedzinie procesorów wielordzeniowych. Generalnie prościej jest skonstruować komputer z jednym szybkim procesorem niż taki, który posiadać będzie wiele wolniejszych procesorów przy tej samej przepustowości maszyny. Jednak prędkość procesora wzrasta głównie poprzez zmniejszanie układów elektrycznych. Współczesne procesory ciągle naciskają limity fizycznego rozmiaru i wytwarzanego podczas pracy ciepła. Te czynniki spowodowały odwrócenie równania wydajności i sprawiły, że rozwój technologiczny kierunkuje się na tworzenie wieloprocesorowych systemów, nawet w komputerach osobistych. Koszt lub złożoność algorytmów szeregowych jest szacowany w oparciu o przestrzeń (pamięć) i czas (cykle procesora), które one zajmują. Algorytmy równoległe, w celu optymalizacji potrzebują jeszcze czegoś więcej – jest to komunikacja pomiędzy różnymi procesorami. Istnieją dwa sposoby takiej komunikacji: pamięć dzielona i przesyłanie komunikatów. Wykorzystywanie pamięci dzielonej wymaga dodatkowo blokowania danych, co zwiększa ogólny koszt o dodatkowy procesor i cykle magistrali, jak również szereguje część algorytmu. Przesyłanie komunikatów podnosi koszt na magistrali oraz dodatkowej pamięci do kolejkowania i przechowywania komunikatów. Projekty procesorów równoległych wykorzystują specjalne magistrale krzyżowe co zmniejsza koszty, ale to algorytm równoległy decyduje o rozmiarze natężenia przepływu danych. Innym problemem związanym z algorytmami równoległymi jest właściwe rozłożenie obliczeń. Np. sprawdzanie każdej liczby od 1 do 100 000 czy jest liczbą pierwszą jest proste do podzielenia pomiędzy procesory, aczkolwiek niektóre procesory dostaną więcej pracy niż inne, co spowoduje ich bezczynne oczekiwanie na zakończenie pracy tych bardziej obłożonych. - podtyp algorytmów równoległych – są zaprojektowane do pracy na klastrach i w środowiskach obliczeń rozproszonych, gdzie przekraczają możliwości klasycznych algorytmów równoległych.wości klasycznych algorytmów równoległych.
, 在計算機科學中，平行演算法（英語：Parallel algorithm），或並行演算法（英語：concurrent algorithm），是一種演算法，將計算程序分解成許多更小的步驟，並將這些步驟交由不同的運算裝置，同時進行運算，之後將運算結果合併，求出解答。與傳統的循序演算法不同，因為它可以改善多核心處理器架構下的運算速度，而日漸受到重視。
, الخوارزمية المتوازية في عالم الحاسب الآلي … الخوارزمية المتوازية في عالم الحاسب الآلي نوع من الخوارزميات التي يمكن فيها تنفيذ أكثر من قطعة في وقت واحد أو تنفيذ قطعة منها على أكثر من وحدة معالجة على أن يتم في نهاية الحصول على النتيجة الصحيحة. وتقابل الخوارزمية المتوازية الخوارزمية التقليدية المتسلسلة حيث يتم تنفيذ التعليمات تباعا. بعض الخوارزميات هي من السهل تقسيمها إلى أجزاء من هذا القبيل. على سبيل المثال، يمكن تقسيم العمل الساعي لتحديد الأعداد الأولية المحصور بين 1 و100000 واحد بتعيين مجموعات فرعية من الأعداد توزع على المعالجات المتوفرة، وبعد ذلك وضع قائمة من النتائج الإيجابية معا مرة أخرى. ومن ناحية أخرى، معظم الخوارزميات المتاحة لحساب بي (π) لا يمكن تقسيمها بسهولة إلى أجزاء متوازية. لأنها تحتاج لنتائج خطوة سابقة للعمل على نحو فعال في الخطوة التالية. وهذه المشاكل تسمى مشاكل ذات طبيعة متسلسلة. الطرائق العددية التكرارية، مثل طريقة نيوتن، هي أيضا خوارزميات ذات طبيعة متسلسلة. بعض المشاكل من الصعب جدا التوازي فيها على الرغم من أنها متكررة recursive problems. أصبحت الخوارزميات المتوازية ذات قيمة بسبب التحسينات الجوهرية في أنظمة المعالجة المتعددة وظهور المعالجات متعددة النوى. بشكل عام، من الأسهل بناء جهاز حاسوب بمعالج سريع واحد على حاسوب مع العديد من المعالجات البطيئة مع الإنتاجية نفسها. لكن زيادة سرعة المعالج تتم عن طريق تقليص حجم الدوائر في المقام الأول، والمعالجات الحديثة ترفع الحجم المادي وحدود الحرارة. هذه الحواجز المرتبطة قلبت المعادلة، مما يجعل المعالجة المتعددة عملية حتى بالنسبة للأنظمة الصغيرة.لمتعددة عملية حتى بالنسبة للأنظمة الصغيرة.
|
| rdfs:comment |
Парале́льний алгори́тм в інформатиці (тако … Парале́льний алгори́тм в інформатиці (також конкурентний алгоритм), на відміну від традиційного послідовного, це алгоритм, який одночасно може виконуватися на багатьох обчислювальних приладах, з наступним об'єднанням отриманих результатів для отримання вірного загального результату. Системи зі спільною пам'яттю вимагають введення додаткових блокувань для даних, що обробляються, і накладають певні обмеження під час використання додаткових процесорів.ід час використання додаткових процесорів.
, Ein paralleler Algorithmus ist ein Algorit … Ein paralleler Algorithmus ist ein Algorithmus, welcher zum Beispiel ein Problem der Komplexitätsklasse NC (Nick’s Class nach Nick Pippenger) in polynomieller Zeit lösen bzw. entscheiden kann. Jeder parallele Algorithmus kann auch sequentiell abgearbeitet werden. Umgekehrt sind auch viele bekannte sequentielle Algorithmen parallelisierbar, so z. B. einige bekannte Sortieralgorithmen wie Bubblesort oder Quicksort. Es gehört jedoch zu den offenen Fragen der theoretischen Informatik, ob alle Algorithmen, welche Probleme der Klassen P oder NP entscheiden, auch parallelisierbar sind. Für viele dieser Algorithmen wurde noch kein entsprechender paralleler Algorithmus gefunden, so dass die meisten Forscher heute davon ausgehen, dass dieses nicht der Fall ist. Zur Untersuchung paralleler Algorithmest. Zur Untersuchung paralleler Algorithme
, В информатике параллельный алгоритм, проти … В информатике параллельный алгоритм, противопоставляемый традиционным последовательным алгоритмам, — алгоритм, который может быть реализован по частям на множестве различных вычислительных устройств с последующим объединением полученных результатов и получением корректного результата. Системы с общей памятью требуют введения дополнительных блокировок для обрабатываемых данных, налагая определённые ограничения при использовании дополнительных процессоров. использовании дополнительных процессоров.
, 在計算機科學中，平行演算法（英語：Parallel algorithm），或並行演算法（英語：concurrent algorithm），是一種演算法，將計算程序分解成許多更小的步驟，並將這些步驟交由不同的運算裝置，同時進行運算，之後將運算結果合併，求出解答。與傳統的循序演算法不同，因為它可以改善多核心處理器架構下的運算速度，而日漸受到重視。
, 並列アルゴリズム（へいれつアルゴリズム、英語: parallel algorithm）とは、アルゴリズムの各部分を異なる複数の処理装置（プロセッサ）上で実行し、最終的にそれらの結果を集めることで答えを得るアルゴリズム。
, Algorytm równoległy - algorytm, który w da … Algorytm równoległy - algorytm, który w danej chwili pozwala na wykonywanie wielu operacji. Równoległe algorytmy są cenne ze względu na możliwość szybszego (w stosunku do jednego procesora) obliczania różnego typu zagadnień. Przy aktualnym stanie rozwoju procesorów dużo łatwiejsze jest połączenie wielu słabszych procesorów od stworzenia nowego o podobnej mocy obliczeniowej. Koszt algorytmów obliczany jest na podstawie wykonanej pracy (ilości cykli wszystkich procesorów), czasu działania i pamięci potrzebnej do działania.iałania i pamięci potrzebnej do działania.
, En las ciencias de la computación, un algo … En las ciencias de la computación, un algoritmo paralelo, en oposición a los algoritmos clásicos o , es un algoritmo que puede ser ejecutado por partes en el mismo instante de tiempo por varias unidades de procesamiento, para finalmente unir todas las partes y obtener el resultado correcto. La técnica memoria compartida necesita del uso de cerrojos en los datos para impedir que se modifique simultáneamente por dos procesadores, por lo que se produce un coste extra en ciclos de CPU desperdiciados y ciclos de bus. También obliga a serializar alguna parte del algoritmo.a a serializar alguna parte del algoritmo.
, In computer science, a parallel algorithm, … In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can do multiple operations in a given time. It has been a tradition of computer science to describe serial algorithms in abstract machine models, often the one known as random-access machine. Similarly, many computer science researchers have used a so-called parallel random-access machine (PRAM) as a parallel abstract machine (shared-memory).parallel abstract machine (shared-memory).
, الخوارزمية المتوازية في عالم الحاسب الآلي … الخوارزمية المتوازية في عالم الحاسب الآلي نوع من الخوارزميات التي يمكن فيها تنفيذ أكثر من قطعة في وقت واحد أو تنفيذ قطعة منها على أكثر من وحدة معالجة على أن يتم في نهاية الحصول على النتيجة الصحيحة. وتقابل الخوارزمية المتوازية الخوارزمية التقليدية المتسلسلة حيث يتم تنفيذ التعليمات تباعا. بعض الخوارزميات هي من السهل تقسيمها إلى أجزاء من هذا القبيل. على سبيل المثال، يمكن تقسيم العمل الساعي لتحديد الأعداد الأولية المحصور بين 1 و100000 واحد بتعيين مجموعات فرعية من الأعداد توزع على المعالجات المتوفرة، وبعد ذلك وضع قائمة من النتائج الإيجابية معا مرة أخرى.ع قائمة من النتائج الإيجابية معا مرة أخرى.
|
