ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.10.2023
Просмотров: 30
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Parallel Processing
Parallel Processing, computer technique in which multiple operations are carried out simultaneously. Parallelism reduces computational time. For this reason, it is used for many computationally intensive applications such as predicting economic trends or generating visual special effects for feature films.
Two common ways that parallel processing is accomplished are through multiprocessing or instruction-level parallelism. Multiprocessing links several processors—computers or microprocessors (the electronic circuits that provide the computational power and control of computers)—together to solve a single problem. Instruction-level parallelism uses a single computer processor that executes multiple instructions simultaneously.
If a problem is divided evenly into ten independent parts that are solved simultaneously on ten computers, then the solution requires one tenth of the time it would take on a single nonparallel computer where each part is solved in sequential order. Many large problems are easily divisible for parallel processing; however, some problems are difficult to divide because their parts are interdependent, requiring the results from another part of the problem before they can be solved.
Portions of a problem that cannot be calculated in parallel are called serial. These serial portions determine the computation time for a problem. For example, suppose a problem has nine million computations that can be done in parallel and one million computations that must be done serially. Theoretically, nine million computers could perform nine-tenths of the total computation simultaneously, leaving one-tenth of the total problem to be computed serially. Therefore, the total execution time is only one-tenth of what it would be on a single nonparallel computer, despite the additional nine million processors.
| PARALLEL ARCHITECTURE |
In 1966 American electrical engineer Michael Flynn distinguished four classes of processor architecture (the design of how processors manipulate data and instructions). Data can be sent either to a computer's processor one at a time, in a single data stream, or several pieces of data can be sent at the same time, in multiple data streams. Similarly, instructions can be carried out either one at a time, in a single instruction stream, or several instructions can be carried out simultaneously, in multiple instruction streams.
Serial computers have a Single Instruction stream, Single Data stream (SISD) architecture. One piece of data is sent to one processor. For example, if 100 numbers had to be multiplied by the number 3, each number would be sent to the processor, multiplied, and the result stored; then the next number would be sent and calculated, until all 100 results were calculated. Applications that are suited for SISD architectures include those that require complex interdependent decisions, such as word processing.
A Multiple Instruction stream, Single Data stream (MISD) processor replicates a stream of data and sends it to multiple processors, each of which then executes a separate program. For example, the contents of a database could be sent simultaneously to several processors, each of which would search for a different value. Problems well-suited to MISD parallel processing include computer vision systems that extract multiple features, such as vegetation, geological features, or manufactured objects, from a single satellite image.
A Single Instruction stream, Multiple Data stream (SIMD) architecture has multiple processing elements that carry out the same instruction on separate data. For example, a SIMD machine with 100 processing elements can simultaneously multiply 100 numbers each by the number 3. SIMD processors are programmed much like SISD processors, but their operations occur on arrays of data instead of individual values. SIMD processors are therefore also known as array processors. Examples of applications that use SIMD architecture are image-enhancement processing and radar processing for air-traffic control.
A Multiple Instruction stream, Multiple Data stream (MIMD) processor has separate instructions for each stream of data. This architecture is the most flexible, but it is also the most difficult to program because it requires additional instructions to coordinate the actions of the processors. It also can simulate any of the other architectures but with less efficiency. MIMD designs are used on complex simulations, such as projecting city growth and development patterns, and in some artificial-intelligence programs.
| Parallel Communication |
Another factor in parallel-processing architecture is how processors communicate with each other. One approach is to let processors share a single memory and communicate by reading each other's data. This is called shared memory. In this architecture, all the data can be accessed by any processor, but care must be taken to prevent the linked processors from inadvertently overwriting each other's results.
An alternative method is to connect the processors and allow them to send messages to each other. This technique is known as message passing or distributed memory. Data are divided and stored in the memories of different processors. This makes it difficult to share information because the processors are not connected to the same memory, but it is also safer because the results cannot be overwritten.
In shared memory systems, as the number of processors increases, access to the single memory becomes difficult, and a bottleneck forms. To address this limitation, and the problem of isolated memory in distributed memory systems, distributed memory processors also can be constructed with circuitry that allows different processors to access each other's memory. This hybrid approach, known as distributed shared memory, eliminates the bottleneck and sharing problems of both architectures.
| COST OF PARALLEL COMPUTING |
Parallel processing is more costly than serial computing because multiple processors are expensive and the speedup in computation is rarely proportional to the number of additional processors.
MIMD processors require complex programming to coordinate their actions. Finding MIMD programming errors also is complicated by time-dependent interactions between processors. For example, one processor might require the result from a second processor's memory before that processor has produced the result and put it into its memory. This results in an error that is difficult to identify.
Programs written for one parallel architecture seldom run efficiently on another. As a result, to use one program on two different parallel processors often involves a costly and time-consuming rewrite of that program.
| FUTURE TRENDS AND APPLICATIONS |
When a parallel processor performs more than 1000 operations at a time, it is said to be massively parallel. In most cases, problems that are suited to massive parallelism involve large amounts of data, such as in weather forecasting, simulating the properties of hypothetical pharmaceuticals, and code breaking. Massively parallel processors today are large and expensive, but technology soon will permit an SIMD processor with 1024 processing elements to reside on a single integrated circuit.
Researchers are finding that the serial portions of some problems can be processed in parallel, but on different architectures. For example, 90 percent of a problem may be suited to SIMD, leaving 10 percent that appears to be serial but merely requires MIMD processing. To accommodate this finding two approaches are being explored: heterogeneous parallelism combines multiple parallel architectures, and configurable computers can change their architecture to suit each part of the problem.
In 1996 International Business Machines Corporation (IBM) challenged Garry Kasparov, the reigning world chess champion, to a chess match with a supercomputer called Deep Blue. The computer utilized 256 microprocessors in a parallel architecture to compute more than 100 million chess positions per second. Kasparov won the match with three wins, two draws, and one loss. Deep Blue was the first computer to win a game against a world champion with regulation time controls. Some experts predict these types of parallel processing machines will eventually surpass human chess playing ability, and some speculate that massive calculating power will one day substitute for intelligence. Deep Blue serves as a prototype for future computers that will be required to solve complex problems.
Параллельная обработка, компьютерная техника, в которой многочисленные операции выполняются одновременно. Параллелизм сокращает время вычислений. По этой причине, он
используется для многих приложений, требующих большого объема вычислений, таких как прогнозирование экономических тенденций и создания визуальных спецэффектов для художественных фильмов.
Два распространенных способа, которые осуществляют параллельной обработки через многопроцессорную обработку или параллелизм на уровне команд. Многопроцессорная обработка связывает несколько процессоров - компьютеры или микропроцессоры (электронные схемы, которые обеспечивают вычислительную мощность и контроль над компьютерами) - вместе, чтобы решить одну проблему. Параллелизм на уровне инструкций использует один процессор компьютера, который выполняет несколько команд одновременно.
Если проблема делится равномерно на десять независимых частей, которые решаются одновременно на десяти компьютерах, то решение требует одну десятую часть времени, которое потребуется на одном непараллельном компьютере, где каждая часть решается в последовательном порядке. Многие крупные проблемы легко делятся для параллельной обработки; Тем не менее, некоторые проблемы трудно разделить, потому что их части являются взаимозависимыми, требуя результатов от другой части проблемы, прежде чем они могут быть решены.
Части проблемы, которые не могут быть вычислены параллельно называются последовательными. Эти последовательные части определяют время вычисления для задачи. Например, предположим, что проблема имеет девять миллионов вычислений, которые могут выполняться параллельно и один миллион вычислений, которые необходимо выполнить последовательно. Теоретически, девять миллионов компьютеров могли бы выполнить девять десятых от общего вычисления одновременно, оставляя одну десятую часть общей проблемы, которую необходимо вычислить последовательно. Таким образом, общее время выполнения составляет лишь одну десятую часть того, что было бы на одном непараллельном компьютере, несмотря на дополнительные девять миллионов процессоров.
ПАРАЛЛЕЛЬНАЯ АРХИТЕКТУРА
В 1966 году американский инженер-электрик Майкл Флинн выделил четыре класса архитектуры процессора (конструкции того, как процессоры манипулируют данными и инструкциями). Данные могут быть переданы либо в процессор компьютера по одному за раз, в одиночный поток данных, либо несколько элементов данных могут быть отправлены в то же время, в множественные потоки данных. Точно так же, инструкции могут быть выполнены либо по одному за раз, в одиночном потоке команд, либо
несколько инструкций могут выполняться одновременно, в множественных потоках команд.
Последовательные компьютеры имеют одиночный поток команд, одиночный поток данных (SISD) архитектуры. Одна часть данных отправляется к одному процессору. Например, если 100 чисел должны быть умножены на число 3, каждый номер будет направлен к процессору, умножен, и результат сохранен; то следующий номер будет отправлен и вычислен, пока не будут вычислены все 100 результатов. Приложения, которые подходят для архитектур SISD включают те, которые требуют сложных взаимозависимых решений, таких как обработка текстов.
Процессор множественного потока команд, одиночного потока данных (MISD) воспроизводит поток данных и посылает его на несколько процессоров, каждый из которых затем выполняет отдельную программу. Например, содержания базы данных могут быть отправлены одновременно нескольким процессорам, каждый из которых будет искать разное значение. Проблемы хорошо подходящие для параллельной обработки MISD включают системы технического зрения, которые извлекают несколько характеристик, таких как растительность, геологические характеристики или производственные объекты, из одного спутникового изображения.
Архитектура одиночного потока команд, множественного потока данных (SIMD) имеет несколько элементов обработки, которые выполняют одну и ту же инструкцию по отдельным данным. Например, машина SIMD со 100 элементами обработки может одновременно умножить 100 чисел каждая по числу 3. SIMD процессоры программируются так же, как процессоры SISD, но их операции выполняются с массивами данных, а не отдельными значениями. SIMD процессоры также известны как матричные процессоры. Примеры приложений, которые используют SIMD архитектуры - повышение обработки изображений и обработки радиолокаций для управления воздушным движением.
Процессор множественного потока команд, множественного потока данных (MIMD) имеет отдельные инструкции для каждого потока данных. Эта архитектура является наиболее гибкой, но и наиболее трудно программируемой, поскольку она требует дополнительных инструкций для координации действий процессоров. Она также может имитировать любой из других архитектур, но с меньшей эффективностью. MIMD конструкции используются на сложных симуляциях, таких как выступающие модели роста и развития города, а также в некоторых программах искусственного интеллекта.
Параллельная связь
Еще одним фактором в архитектуре параллельной обработки явл. то, как процессоры взаимодействуют друг с другом. Один из подходов заключается в том, чтобы позволить процессорам совместно использовать одну память и общаться, читая данные друг друга. Это называется совместной памятью. В этой архитектуре все данные могут быть доступны любому процессору, но необходимо соблюдать осторожность, чтобы не допустить связанным процессорам непреднамеренного перезаписать результаты друг друга.
Альтернативный метод - подключение процессоров и позволяют им отправлять сообщения друг другу. Этот метод известен как передача сообщений или распределенная память. Данные разделены и сохраняются в памяти разных процессоров. Это затрудняет обмен информацией, так как процессоры не подключены к той же памяти, но это и безопаснее, потому что результаты не могут быть перезаписаны.
В системах с общей памятью с увеличением числа процессоров доступ к единой памяти становится затруднительным, и узкие формы. Для устранения этого ограничения и проблемы изолированной памяти в системах с распределенной памятью процессоры с распределенной памятью также могут быть построены со схемой, которая позволяет разным процессорам доступ к памяти друг друга. Этот гибридный подход, известный как распределенная совместно используемая память, устраняет узкие места и проблемы совместного использования обеих архитектур.
СТОИМОСТЬ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ
Параллельная обработка является более дорогостоящей, чем последовательные вычисления, так как несколько процессоров являются дорогостоящими и увеличение скорости вычислений редко пропорционально числу дополнительных процессоров.
Процессоры MIMD требуют сложного программирования для координации своих действий. Нахождение ошибок программирования MIMD также осложняется зависящими от времени взаимодействий между процессорами. Например, один процессор может потребовать результат из памяти второго процессора, прежде чем процессор производит результат, и поместить его в свою память. Это приводит к ошибке, что трудно идентифицировать.