что такое параллельный и последовательный код

Последовательный и паралельный код

Устройства, работающие с числами в последовательном коде, называются устройствами последовательного действия. Они имеют по одному входу и выходу для приема и передачи каждого n-разрядного числа.

Устройства, работающие с параллельным n-разрядным кодом, называются устройствами параллельного действия. Они имеют п входов и выходов для каждого n-разрядного числа.

Имеются устройства и смешанного типа, в которых, например, входное число представляется в параллельной форме, а выходное — в последовательной.

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

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

Цифровые автоматы отличаются от комбинационных устройств тем, что они обладают памятью и хранят сведения о предшествующих тактах работы.

Источник

ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ ФИЗИЧЕСКИМИ СИГНАЛАМИ

ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ ЭВМ

Физическими аналогами зна­ков 0 и 1 двоичного алфавита служат сигналы, способные принимать два хорошо различимых значения, например, напря­жение (потенциал) высокого и низкого уровней, отсутствие и наличие электрического импульса, противоположные по зна­ку значения магнитной индукции и т. п.

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

В цифровых вычислительных устройствах обычно приме­няют потенциальный и импульсный способы физического пред­ставления информации.

Рис. 2.1. Способы представления цифровой информации:

При потенциальном способе (рис 2.1, а) двум значениям переменной 1 и 0 соответствуют разные уровни напряжения в соответствующей точке схемы машины (потенциальный код). Потенциальный сигнал сохраняет постоянный уровень в тече­ние такта, а его значение в переходные моменты не является определенным.

При импульсном способе представления информации (рис. 2.1,б) единичное и нулевое значения двоичной переменной отображаются наличием и отсутствием электрического импульса или разнополярными импульсами в соответствующей точке схемы (импульсный код).Импульсный сигнал можно характеризовать амплитудой Um, продолжительностью импульса по основанию t_осн, дли­тельностью фронта t_фр и среза t_cp

Аналогичные понятия могут быть применены к потенциаль­ному сигналу (рис. 2.1, а). Потенциальный сигнал характери­зуется, кроме того, разностью Uc верхнего и нижнего уровней напряжения. Понятия фронта и среза у потенциального сигнала всегда связаны с процессом перехода соответственно от нижне­го к верхнему и от верхнего к нижнему уровню напряжений.

В соответствии с типом используемых сигналов для пред­ставления информации схемы цифровых устройств принято де­лить на импульсные, потенциальные и импульсно-потен­циальные.

Слово может быть представлено последовательным или па­раллельным кодом.

При последовательном коде каждый временной такт пред­назначен для отображения одного разряда кода слова (рис. 2.2). В этом случае все разряды слова фиксируются по очереди од­ним и тем же элементом и проходят через одну линию переда­чи информации.

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

При параллельной передаче информации код слова раз­вертывается не во времени, а в пространстве, так как значения всех разрядов слова передаются по нескольким линиям одно­временно (рис. 2.3).

Рис. 2.2. Последовательный им­пульсный код (в)

и последова­тельный потенциальный код (б)

Рис. 2.3. Параллельный им­пульсный код (а)
и параллельный потенциальный код (б)

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

В современных ЭВМ основные устройства, уча­ствующие в обработке информации, для достижения высокого быстродействия строятся как параллельные, хотя они и тре­буют большего объема аппаратуры. Для экономии оборудова­ния в некоторых устройствах применяют последовательно-па­раллельный код, при котором слова разбиваются на части (слоги) и передача, а иногда и обработка производятся после­довательно слог за слогом. При этом каждый слог предста­вляется параллельным кодом.

Источник

Введение в цифровую электронику

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

Далее в основном используются термины «напряжение высокого и низкого уровня» (сигналы высокого и низкого уровня), соответствующие уровням логической 1 и логического 0.

Информация в цифровых устройствах может быть представлена в последовательном и параллельном кодах. При использовании последовательного кода каждый такт соответствует одному разряду двоичного кода. Номер (разряда определяется номером такта, отсчитываемого от такта, совпадающего с началом представления кода. Графики, показанные на рисунок 1, иллюстрируют последовательный код байтового двоичного числа 10011011 при потенциальном и импульсном способах представления информации. При первом способе рисунок 1,а сигнал сохраняет низкий или высокий уровни в течение одного или нескольких тактов. В моменты перехода сигнала от одного уровня к другому его значение является неопределенным. При импульсном способе представления цифровой информации рисунок 1,б единичному и нулевому значению двоичной переменной соответствует наличие или отсутствие импульса конечной длительности. При последовательном коде числа все его разряды могут быть зафиксированы на одном элементе и переданы по одному каналу передачи информации. Для передачи всего числа требуется восемь тактов рисунок 1,в.

Параллельный код позволяет существенно сократить время обработки для передачи информации. Для примера рисунок 3 иллюстрирует параллельный код семиразрядного числа 1101101. В этом случае как при импульсном рисунок 2,а, так и при потенциальном рисунок 2,б способах представления информации все разряды двоичного кода представлены в одном временном такте, могут фиксироваться отдельными элементами и передаваться по раздельным каналам (разрядным шинам). Цифровые устройства производящие обработку и преобразование поступающей на их входы информации, называют цифровыми автоматами. Задача построения цифрового автомата, выполняющего определенные действия над двоичными сигналами, заключается в выборе элементов и способа их соединения, обеспечивающих заданное преобразование. Эти задачи решает математическая логика или алгебра логики (булева математика). Устройства, формирующие функции булевой математики, называют логическим или цифровыми и классифицируют по различным отличительным признакам. Цифровые устройства по характеру информации на входах и выходах подразделяют на устройства последовательного, параллельного и смешанного действия.

Примером последовательного устройства может быть счетчик импульсов, состояние выходов которого зависят от общего числа поступивших на его вход импульсов

Источник

Параллельный и последовательный код. Поясните что это и для чего служит

Тема 5-1

5. Все волны можно разделить на два типа: упругие и электромагнитные. Поясните кратко.

Электромагнитная волна представляет собой процесс последовательного, взаимосвязанного изменения векторов напряжённости электрического и магнитного полей, направленных перпендикулярно лучу (направлению) распространения волны, при котором изменение электрического поля вызывает изменения магнитного поля, которые, в свою очередь, вызывают изменения электрического поля. Электромагнитная волна характеризуется наличием трёх взаимно перпендикулярных (в вакууме) векторов: вектора скорости, вектора напряжённости электрического поля и вектора магнитной индукции (напряжённости магнитного поля H).

Ионизация и возбуждение. Поясните.

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

Тема 5-2

Параллельный и последовательный код. Поясните что это и для чего служит.

Слова – это группы битов, которые могут быть прочитаны и интерпретированы. Слово может быть представлено в параллельном виде (коде). Как при импульсном, так при потенциальном способе представления информации все разряды двоичного числа (все биты) представлены одновременно (в одном временном промежутке, такте). В этом случае для их передачи необходимо задействовать количество потенциальных проводов, соответствующих количеству разрядов, и один проводник, имеющий нулевой потенциал (говорят, надо использовать шину).

Если слово представлено в последовательном коде, то для его передачи нужен один канал (два проводника – потенциальный и нулевой) и требуется 8 тактов для передачи всего слова. Скорость передачи информации при этом меньше.

57. Поясните понятие: передача данных, канал связи. Приведите примеры для них.

Передача данных — физический перенос данных в виде сигналов от точки к точке или от точки к нескольким точкам средствами электросвязи по каналу связи, как правило, для последующей обработки средствами вычислительной техники. Примерами применения передачи данных являются Код Морзе, RS-232, RS-423, RS-485, I²C, USB, FireWire, Ethernet и т.д.

Канал связи — система технических средств и среда распространения сигналов для односторонней передачи данных от источника к получателю. Два канала связи, обеспечивающих передачу данных между узлами во взаимопротивоположных направлениях, образуют канал передачи данных. Существует множество видов каналов связи, среди которых наиболее часто выделяют каналы проводной связи (воздушные, кабельные, световодные и др.) и каналы радиосвязи (тропосферные, спутниковые и др.).

38. Заданы два числа в двоичной системе счисления. Они представляют собой аргументы логической функции. Определить, как будет выглядеть значение логической функции для элемента ИЛИ – НЕ. Его таблица истинности

ЛЭ ИЛИ реализует функцию логического сложения (дизъюнкцию) дизъюнкцию)

Y=X1+X2=X1VX2, где обозначение V от латинского VEC – ИЛИ.

Инвертор (элемент «НЕ» (NOT)) выполняет логическую функцию инверсия:

Черта над х указывает на то, что логический сигнал инвертирован. Он имеет один вход и один выход. На вход такого ЛЭ воздействует активный уровень сигнала – уровень, при котором сигнал производит воздействие на элементы электронной схемы. Проходя через инвертор сигнал меняет свой активный уровень. Если последовательно включить два инвертора, то получим логический повторитель Y=X.

Источник

От последовательного кода к параллельному за пять шагов c Intel® Advisor XE

Если вы давно разрабатываете многопоточные приложения, наверняка вы сталкивались с распараллеливанием уже существующего последовательного кода. Или наоборот, вы новичок в параллельном программировании, а перед вами встали задачи оптимизации проекта и улучшения масштабируемости, которые тоже могут быть решены путём распараллеливания отдельных участков программы.

Новый инструмент Intel Advisor XE поможет вам распараллелить приложение, потратив на это минимум сил и времени.

Advisor XE вышел в свет в сентябре этого года в составе пакета для разработчиков Intel Parallel Studio XE 2013. Дословный перевод названия – «советчик» — довольно ёмко описывает его предназначение. Инструмент помогает программисту проанализировать возможности распараллеливания кода: найти наиболее подходящие для этого участки и оценить предполагаемый полезный эффект – а стоит ли вообще за это браться? Кроме того, Advisor XE подскажет, где могут возникнуть ошибки, такие как гонки данных. И всё этого без реальной модификации программы! Но обо всём по порядку.

Advisor XE выпускается для Windows* и Linux* и работает с языками C++, C# и Fortran. В этом посте я буду пользоваться версией под Windows* — в ней есть удобная интеграция в Microsoft Visual Studio* (для желающих есть и собственный интерфейс без интеграции). В качестве примера я взял программу Tachyon, входящую в набор примеров Advisor XE. Она осуществляет 2D рендеринг и трассировку лучей, выдавая такую картинку:

В Visual Studio Advisor XE добавляет свою панель инструментов, предоставляющую быстрый доступ к его функциям. Итак, открываем свой проект, строим его в режиме «Release» и открываем “Advisor XE Workflow”:

Advisor XE Workflow проводит разработчика через пять этапов оценки приложения, после которых он сможет принять осмысленное решение, стоит ли распараллеливать этот код и в каком месте это лучше сделать.

Этап 1. Профилировка (Survey Target)

Первое, что делает Advisor XE – запускает ваше приложение и профилирует его, т.е. оценивает производительность и ищет «горячие точки» — функции, циклы и отдельные инструкции, потребляющие большую часть ресурсов процессора. Это нужно для того, чтобы сконцентрировать усилия на самых критичных для производительности участках, поскольку их распараллеливание принесёт наибольший эффект. Для начала профилировки нажимаем кнопку «Collect Survey Data» в окне Advisor XE Workflow:

Advisor XE запускает приложение, дожидается окончания работы и «финализирует» собранные данные. После этого пользователю предоставляется список функций и мест в коде в иерархическом виде, для каждого из которых отображается время CPU в секундах и процентах. Отдельно показано собственное время функции и время, включающее вложенные функции:

Те места, где «горячей точкой» является цикл, помечены специальным значком. Это удобно, т.к. циклы часто становятся объектом распараллеливания, если они, например, обрабатывают большие объёмы независимых данных.

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

В нашем примере мы остановим выбор на самой верхней по стеку вызовов функции, содержащей цикл – parallel_thread. На неё (включая вложенные функции) приходится 80,9% затраченного процессорного времени. Кстати, двойной клик на «горячую» функцию переведёт вас к просмотру исходников, где тоже будет информация об использовании CPU, но уже для конкретных строк кода.

Этап 2. Аннотации (Annotate Sources)

Когда первое предположение о будущем внедрении многопоточности сделано, нужно сообщить об этом «советчику». Для этого используются так называемые аннотации – специальные макросы (или вызовы функций, в зависимости от языка), понятные Advisor-у, но не влияющие на функционирование вашей программы.

В Visual Studio аннотации добавляются с помощью контекстного меню – просто выделяете понравившийся блок кода и запускаете Annotation Wizard:

Аннотации Advisor XE бывают нескольких типов. Для моделирования распараллеливания цикла нам пригодятся два основных – “Annotate Site” и “Annotate Task”.

“Annotate Site” используется для отметки границ параллельного региона в коде. Для С++ она представлена макросами ANNOTATE_SITE_BEGIN и ANNOTATE_SITE_END. В нашем примере мы будем распараллеливать цикл for, разбивая пространство итераций на более мелкие порции, с тем, чтобы каждая такая порция могла исполняться параллельно с другими.

“Annotate Task” используется для разметки границ одной задачи, с помощью макросов ANNOTATE_TASK_BEGIN и ANNOTATE_TASK_END. Задачей считается блок кода, который может быть исполнен многократно разными потоками. Задачи исполняются параллельно с другими задачами и остальным кодом в параллельном регионе.

Итак, приступаем к разметке. Весь цикл for заключим в параллельный регион. А тело цикла обозначим как задачу, т.к. оно будет исполняться параллельно (в модели) над разными итерациями:

Чтобы С++ программа скомпилировалась с аннотациями, нужно подключить заголовочный файл advisor-annotate.h.

Этап 3. Проверка эффективности (Check Suitability)

На третьем шаге Advisor XE делает повторную профилировку. Отличие от первой профилировки состоит в том, что теперь собирается не информация о «горячих функциях», а моделируется параллельное исполнение приложения и оценивается его потенциальная скорость работы.

Исполняется программа точно так же, как и без аннотаций – в однопоточном режиме. Скорость работы и корректность результатов не страдают. Однако аннотации дают возможность инструменту смоделировать многопоточное исполнение аннотированного кода и выдать оценку эффективности в цифрах на суд программиста:

Справедливости ради нужно сказать, что результаты далеко не всегда будут такими радужными. Может оказаться, что прогнозируемый положительный эффект от распараллеливания совсем не так высок, или вовсе нулевой. Но этот результат тоже будет полезным, т.к. вы убедитесь в неэффективности выбранного подхода, и будете искать другие пути. В этом и состоит предназначение Advisor XE – дать возможность попробовать множество подходов к распараллеливанию, потратив минимум сил и времени, и выбрать лучший.

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

Этап 4. Проверка корректности (Check Correctness)

Превращение однопоточной программы в многопоточную может привести к новым багам – таким как гонки данных. Чтобы облегчить верификацию и отладку в «живой» программе, Advisor XE позволяет провести оценку корректности смоделированного программистом решения. Для этого нужно перекомпилировать программу в режиме “Debug” и запустить проверку корректности Advisor XE – “Check Correctness”.

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

В результате проверки появляется Correctness Report – отчёт об ошибках. Он включает в себя список ошибок, их тип, параллельный регион, в котором они проявляются. Кликнув два раза на ошибку можно перейти к просмотру исходников, где появляется дополнительная информация, например, стеки вызовов:

В нашем примере обнаружилась гонка данных – в функции video::next_frame() инкрементируется глобальная переменная g_updates. Пока на исполнение программы она не влияет, ведь в реальности код всё ещё однопоточный. Однако очевидно, что проблему надо будет устранять, и это скажется на производительности – могут появиться объекты синхронизации, сдерживающие масштабируемость, или наоборот, локализация переменных принесёт положительный эффект.

Чтобы это проверить, в Advisor XE есть ещё один тип аннотаций – “Lock Annotations”. Они используются для моделирования критических секций. В нашем примере g_updates модифицируется в функции video::next_frame(), вызов которого происходит в нашем распараллеливаемом цикле. Поэтому мы можем здесь же защитить её аннотациями синхронизации:

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

Этап 5. Реализация распараллеливания (Add Parallel Framework)

Последний этап распараллеливания кода – собственно распараллеливание, т.е. выбор потокового API, непосредственное кодирование и отладку. Этот шаг лишь условно включён в “workflow” Advisor XE, чтоб не забыть, так сказать. «Советчик» предназначен лишь для моделирования и предоставления разработчику аналитический информации, на основе которой тот будет чётче представлять себе, куда двигаться дальше – что и как стоит модифицировать, какого эффекта ждать и какие проблемы могут возникнуть. Дальше действовать придётся самому.

Но не надо унывать – в пакете Intel Parallel Studio XE есть ещё много инструментов, которые помогут на других этапах. Реализовать параллельный цикл по модели в приведённом примере можно с помощью множества высокоуровневых «параллельных фреймворков», которые позволяют абстрагироваться от самостоятельного создания потоков и распределения нагрузки между ними. Например, преобразовать последовательный цикл в параллельный можно с помощью Intel Cilk Plus. При этом потребуется использовать компилятор Intel. А в качестве примитива синхронизации можно взять tbb::spin_mutex из библиотеки Intel TBB. Код цикла (уже параллельного) при этом будет выглядеть так:

Выводы

Advisor XE будет полезен там, где уже есть работающий код, который нужно частично распараллелить. Например, есть старое научное приложение на Фортране, которое нужно оптимизировать для нового сервера или кластера. Основной плюс инструмента – возможность быстро смоделировать многопоточное исполнение. Проведя несколько экспериментов, можно определить участки кода, на которых стоит сконцентрировать усилия, и понять, чего от этого ждать – насколько распараллеливание может быть полезно, какой масштабируемости можно добиться. Проделать то же самое «по-настоящему», создавая потоки и перекраивая код, отнимет куда больше усилий.

Источник