Geum.ru

Лекция 11

Вид материалаЛекция

Содержание


Операции сдвига
Операции сканирования
Операции пересылки данных
Параллелизм задач
Подобный материал:
1   2   3   4   5   6   7

Операции сдвига


Для эффективной реализации некоторых параллельных алгоритмов требуются операции сдвига массивов. Примерами служат алгоритмы обработки изображений, конечно-разностные алгоритмы и некоторые другие.

Операции сканирования


Операции сканирования еще называются префиксными/суффиксными операциями. Префиксная операция, например, суммирование выполняется следующим образом. Элементы массива суммируются последовательно, а результат очередного суммирования заносится в очередную ячейку нового, результирующего массива, причем номер этой ячейки совпадает с числом просуммированных элементов исходного массива.

Операции пересылки данных


Это, например, операции пересылки данных между массивами разной формы (то есть имеющими разную размерность и разную протяженность по каждому измерению) и некоторые другие.


При программировании на основе параллелизма данных часто используются специализированные языки - CM FORTRAN, C*, FORTRAN+, MPP FORTRAN, Vienna FORTRAN, а также HIGH PERFORMANCE FORTRAN (HPF). HPF основан на языке программирования ФОРТРАН 90, что связано с наличием в последнем удобных операций над массивами (см., например, М.Меткалф и Дж.Рид Описание языка программирования ФОРТРАН 90, М."Мир", 1995).

Параллелизм задач



Стиль программирования, основанный на параллелизме задач подразумевает, что вычислительная задача разбивается на несколько относительно самостоятельных подзадач и каждый процессор загружается своей собственной подзадачей. Компьютер при этом представляет собой MIMD - машину. Аббревиатура MIMD обозначает в известной классификации архитектур ЭВМ компьютер, выполняющий одновременно множество различных операций над множеством, вообще говоря, различных и разнотипных данных. Для каждой подзадачи пишется своя собственная программа на обычном языке программирования, обычно это ФОРТРАН или С. Чем больше подзадач, тем большее число процессоров можно использовать, тем большей эффективности можно добиться. Важно то, что все эти программы должны обмениваться результатами своей работы, практически такой обмен осуществляется вызовом процедур специализированной библиотеки. Программист при этом может контролировать распределение данных между процессорами и подзадачами и обмен данными. Очевидно, что в этом случае требуется определенная работа для того, чтобы обеспечить эффективное совместное выполнение различных программ. По сравнению с подходом, основанным на параллелизме данных, данный подход более трудоемкий, с ним связаны следующие проблемы:

  • повышенная трудоемкость разработки программы и ее отладки;
  • на программиста ложится вся ответственность за равномерную загрузку процессоров параллельного компьютера;
  • программисту приходится минимизировать обмен данными между задачами, так как пересылка данных - наиболее "времяемкий" процесс;
  • повышенная опасность возникновения тупиковых ситуаций, когда отправленная одной программой посылка с данными не приходит к месту назначения.


Привлекательными особенностями данного подхода являются большая гибкость и большая свобода, предоставляемая программисту в разработке программы, эффективно использующей ресурсы параллельного компьютера и, как следствие, возможность достижения максимального быстродействия. Примерами специализированных библиотек являются библиотеки MPI (Message Passing Interface) и PVM (Parallel Virtual Machines). Эти библиотеки являются свободно распространяемыми и существуют в исходных кодах. Библиотека MPI разработана в Аргоннской Национальной Лаборатории (США), а PVM - разработка Окриджской Национальной Лаборатории, университетов штата Теннеси и Эмори (Атланта).


Let us now turn to the question of how a message-passing program might be written by a programmer. The most frequently encountered situation with multicomputers, is for the programmer to write a single source code program that is compiled and linked one a front-end computer. The resulting object code is copied in the local memory of every processor taking part in the computation. The parallel program is executed by having all processors interpret the same object code. This model of parallel computing is known as the Single-Program-Multiple-Data model, or SPMD for short. If all the variables with the same name in every process had the same value and if all these processes only had access to the same data there would be no parallelism at all, each process would act exactly the same as all others. In a message-passing context, the communication interface typically includes a function or a procedure that returns a value identifying the process that called that function or procedure. Further more the same value will always be returned to the same process. For the moment, let us call this returned value the process identifier. Typically the sequence of instructions executed by a process will be determined by the input data and the identifier of that process. As an illustration, consider Figure 14 below which shows the local memory of two processes. The local variables called whoami in each process have been set somehow to the identifier of the corresponding process.

The distinctive feature of the SPMD model is that all processes are of the same type. In theory, this restriction does not affect the expressivity of the message-passing paradigm. All we have to do in order to run different types of processes is to write a conditional statement whose branches call the appropriate code for each process depending on their respective identifier. In practice, there are occasions when the SPMD model is not suitable. For one, under the SPMD model, the executable of every types of process has to be loaded on every processor. Depending on the application, this may place too large a burden on the memory capacity of individual processors. The alternative model of parallel computing that addresses this issue is the Multiple-Program-Multiple-Data model where different executables may be interpreted by distinct processors. The MPMD model assumes the ability to load object code on processors during a parallel computation and is very natural on network of workstations. Many multicomputer vendors simplify their system software by only providing parallel environments which support SPMD parallel programs; the provision for the MPMD model on multicomputers is an active research topic.

Most current multicomputers do not support time-sharing, i.e. multiple processes per processor (some authorities understand the term ``SPMD" to include this further restriction). This is for efficiency reasons and for example the whole computation may come to a grinding halt when all processes need data from some swapped-out process. On the other hand, time-sharing may relieve any need to carefully balance the workload of each processor. Time-sharing on multicomputers is also an active area of research.


Messages are central to the message-passing programming model; they are exchanged between processes. When two processes exchange a message, data is copied from the local memory of one process into the local memory of the other process. The data sent in a message comes under two headings: contents and envelope. The contents of the message is purely user data and is interpreted neither by the communication interface nor by the communication system that lies behind that interface. The data on the envelope however is used by the communication system to copy the contents of the message between local memories; specifically the following information must be specified:
  • Which processor is sending the message.
  • Where is the data on the sending processor.
  • What kind of data is being sent. How much data is there.
  • Which processor(s) are receiving the message.
  • Where should the data be left on the receiving processor.
  • How much data is the receiving processor prepared to accept.

In general the sending and receiving processes will cooperate in providing this information. Some of this information provided by the sending process will be attached to the message as it travels through the system and forms the envelope data. The message passing system may make some of this information available to the receiving process. Other information may be provided by the receiving process.

Message querying functions. As well as delivering data the message passing system has to provide some information about progress of communications. A receiving process will be unable to use incoming data if it is unaware of its arrival. Similarly a sending process may wish to find out if its message has been delivered. Messages are therefore also a means to synchronise processes.

Every day life examples of communication systems/interfaces.The essence of message passing is communication and many of the important concepts can be understood by analogy with the methods that people use to communicate, phone, fax, letter, radio etc. Just as phones and radio provide different kinds of service different message passing systems can also take very different approaches. For the time being we are only interested in general concepts rather than the details of particular implementations.


The simplest form of message is a point-to-point communication in which a message is sent from a sending process to a receiving process. Only these two processes need to know anything about the message. The communication itself is composed of two operations: a send and a receive

The send operation can be either synchronous or asynchronous depending on whether or not it completes before or after the corresponding receive operation has been initiated. Here are some illustrations of these two communication modes.

Synchronous sends complete only when the corresponding message is being taken care of by some receiving process.

Asynchronous sends completes as soon as the corresponding message has been delivered to the communication system.

A fax message or registered mail is a synchronous operation. The sender can find out if the message has been delivered.

A post card is an asynchronous message. The sender only knows that it has been put into the post-box but has no idea if it ever arrives unless the recipient sends a reply.

The main two forms for communication procedures are blocking and non-blocking. They relate the completion times of a communication operation and of the procedure that initiates that communication operation.

Blocking procedures only return when the corresponding communication has completed. An example might be someone placing your telephone call on-hold.

Non-blocking procedures return straight away and allow the process to continue to perform other work. At some later time the process can test for the completion of the corresponding communication.