WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 14 |

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

Рис. 2. Модифицированная структура системы, изображенной на рис. Для реализации подобного буфера предлагается (рис. 2):

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

2) сам буфер реализовать в виде циклического массива строк кэша с разрушающим чтением;

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

Для того чтобы чтение в буфер и запись в него можно было совместить по времени, строки кэша должны быть снабжены информацией о том, готовы ли данные. Быстродействие устройства, записывающего данные в буфер, серьезно превышает быстродействие читающего устройства, которое может сбрасывать данные в системную память: в этом случае необходимо также, чтобы буфер хранил информацию о том, какое количество готовых данных нахоСборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ И СЕТИ дится в основной памяти. Для этого разумно использовать счетчик. На рис. 3 представлен возможный сценарий использования такого буфера (R — флаг готовности/валидности строки буфера, M — счетчик готовых данных в системной памяти, стрелка слева — указатель записи, стрелка справа — указатель чтения).

1 4 Рис. 3. Пример использования буфера В начальный момент времени (1) буфер пуст, в ячейках памяти записано некоторое начальное значение «xxxx». К моменту 2 пишущее устройство записало данные («yyyy») в три строки, установив флаги готовности. В момент 3 были прочитаны две строки, в них сброшены флаги готовности (разрушающее чтение). В момент 4 запись («zzzz») обогнала чтение более чем на размер буфера, и некоторые строки были записаны в основную память. На 5 видно, что при чтении из буфера флаг готовности сбрасывается и в том случае, если счетчик, относящийся к системной памяти, не равен нулю. В момент сброса контроллер буфера может инициировать выборку строки из памяти в буфер. В данном примере, где буфер содержит строк по 4 байта, и используется счетчик по модулю 8, логический размер разделяемой памяти может составлять 256 (848) байт. Если строка буфера состоит из 256 байт, строк (итого — четырехкилобайтный буфер), и с каждой строкой будет ассоциирован 20-битный счетчик (дополнительные 40 байт), то возможно адресовать четырехгигабайтное разделяемое пространство.

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

Стоит отметить, что через этот буфер разумно передавать данные, формирующиеся динамически CPU и GPU, в то время как статические данные, которые могут быть загружены из носителей большого объема (например, жестких дисков) в системную память посредством DMA и оттуда попасть в GPU минуя CPU, разумно загружать напрямую из системной памяти, как это делается сейчас. Эта задача может быть решена либо использованием двух различных интерфейсов у GPU: один для статических (текстур) и один для динамических (код ядер, геометрия) данных, либо посредством того же транслятора виртуальных адресов путем выделения различных диапазонов логических адресов для различных типов данных.

Сборник трудов молодых ученых и сотрудников кафедры ВТ 42 КОМПЬЮТЕРНЫЕ СИСТЕМЫ И СЕТИ Предварительная оценка эффективности предложенного решения Как было сказано, данные, которыми обмениваются CPU и GPU, могут быть разделены на статические и формируемые динамически. Статические данные представляют собой текстуры (для графических задач) либо массивы исходных данных для обработки (для вычислительных задач). Статические данные (texture data на рисунках) в нашей системе идут по интерфейсу, соединяющему системную память с GPU, и соответственно передаются с большой (десятки-сотни тактов) задержкой и меньшей, чем для памяти на кристалле (хотя часто достаточной для того, чтобы не порождать блокировок), пропускной способностью. Динамические данные поступают через транслятор виртуальных адресов в кэш обмена и оттуда адресату.

Простейший цикл взаимодействия CPU (ведущее управляющее устройство) и GPU (подчиненное устройство) состоит из следующих этапов:

1) формирование программы для GPU и прочих динамически формируемых данных, 2) отправка их в буфер и оповещение GPU о наличии данных в буфере, 3) выгрузка данных из буфера и их разбор, формирование расписания, распределение задач по ядрам, 4) исполнение кода с одновременной загрузкой статических данных и выгрузкой результатов в системную память.



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

Рассмотрим коммуникацию в немодифицированной архитектуре. Введем понятие «порция данных» (chunk) — количество байтов, необходимых для загрузки всех ядер GPU (входная порция), либо выдаваемых всеми ядрами GPU в качестве результата (выходная порция).

Введем обозначения:

• TD — время, затрачиваемое на передачу динамических данных;

DRAM • TL — задержка доступа к динамической памяти;

• DD — общее количество динамических данных (байты);

• PDRAM — пропускная способность шины системной памяти (байтов в секунду);

• TC — время, в течение которого производятся сами вычисления, включая пересылку используемых данных;

• Cin — размер входной порции данных;

• Cout — размер выходной порции данных;

• TP — время непосредственной обработки загруженной порции;

• N — количество порций статических данных, используемых в вычислительной задаче.

Время передачи динамических данных можно представить как двойное (на чтение и на запись) время обращения к (системной, DRAM) памяти:

DD DRAM TD =2TL +2.

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

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ И СЕТИ Cin Cin Cout T, DRAM TC = 2TC + + N max,.

P PDRAM PDRAM PDRAM Наличие или отсутствие простоев вследствие медленной передачи динамических данных зависит от соотношения значений этих параметров: если второе время больше первого, то простои невозможны. Посмотрев на разность двух выражений Cin - 2DD Cin Cout T,, TC -TD = + N max, P PDRAM PDRAM PDRAM можно понять, что возникновение простоев вызвано:

1) малым объемом динамических данных в сравнении с порцией статических;

2) значительным временем обработки каждой порции;

3) большим количеством порций.

Кроме того, большой размер порции при неизменном общем объеме статических данных означает уменьшение числа порций и, как следствие, снижение времени вычисления; а для длинных вычислений требуется столь же большой объем динамических данных. Таким образом, можно сказать, что при простых вычислениях над большим объемом данных, хранящихся в системной памяти, введение буфера на кристалле может не дать прироста в производительности. Иначе говоря, введение буфера позволяет увеличить гибкость вычислений: становится возможным давать GPU много разнообразных, разветвленных задач, связанных с обработкой меньших объемов данных. Кроме того, безусловно, возрастает эффективность для задач, в принципе не связанных с обработкой статических данных. Количественно оценить эффект от введения этой системы коммуникации можно либо путем создания HDL-моделей с реальными программами, либо имея статистику о количественном соотношении генерируемых динамически и статических данных в реальных приложениях. К сожалению, найти такую статистику автору не удалось.

Заключение Предложенное решение логично продолжает процесс интеграции разнородных вычислителей на кристалле и позволяет увеличить гибкость вычислительного процесса и несколько отодвинуть «стену памяти». Более подробные данные об эффективности решения может дать моделирование HDL-моделей CPU и GPU. Также остался нерассмотренным вопрос о подключении множества CPU и GPU к одному буферу.

ЛИТЕРАТУРА 1. Boudier P., Seller G. Memory system on fusion APUs // AMD Fusion Developer summit. 2011.

2. Patterson D., Hennessy J. Computer organisation and design. Burlington: Elsevier, 2009. 703 р.

3. ATI Stream computing: programming guide. Advanced Micro Devices Inc. Sunnyvale, 2010.

Сведения об авторах Герасимов Антон Анатольевич — аспирант; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра вычислительной техники; E-mail: tossel@gmail.com Перминов Илья Валентинович — аспирант; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра вычислительной техники; E-mail: i.am.perminov@gmail.com Сборник трудов молодых ученых и сотрудников кафедры ВТ 44 КОМПЬЮТЕРНЫЕ СИСТЕМЫ И СЕТИ УДК 004.ЗАДАЧА ОПТИМИЗАЦИИ ПРИ СЕГМЕНТАЦИИ ПАКЕТОВ В БЕСПРОВОДНЫХ СЕТЯХ А. В. Осипов, Н. И. Фролова Поставлена задача определения оптимального числа кадров, на которые требуется разбить пакет, при заданном уровне вероятности битовой ошибки, чтобы минимизировать объем издержек передачи данных, вызванных ненадежностью канала. Использование оптимальной сегментации позволяет значительно снизить издержки передаваемых данных, вызванные ненадежностью канала.

Ключевые слова: оптимизация, беспроводные сети, сегментация пакетов.

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





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

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

Длина пакета, подлежащего пересылке, составляет lpacket. Длина кадра lcadr определяется исходя из количества кадров k, на которые разбивается исходный пакет длиной lpacket. В случае кодирования с обнаружением ошибок (без возможности их исправления) для детектирования ошибки достаточно единственного бита четности, поэтому parity = 1 бит:

lpacket lcadr(k) = ceil, k где ceil — функция округления вверх до целого; q — вероятность битовой ошибки;

lcadr (k )+ parity p(q) = 1- q — вероятность безошибочности бита; pcadr(q,k) = p(q) — вероятность безошибочности кадра; qcadr(q,k) = 1- pcadr(q,k) — вероятность ошибки в кадре;

ptotal q, k = pcadr q,k + qcadr q, k pcadr q, k + qcadr q, k pcadr q,k + qcadr q,k pcadr q, k +...

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) — вероятность успешной передачи кадра; vp(k) = parity — объем издержек передаваемых данных в случае успешной передачи кадра; vq(k) = vp(k)+ parity + lcadr(k) — объем издержек передаваемых данных в случае повторной передачи кадра.

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ И СЕТИ Суммарный объем издержек передаваемых данных, вызванных ненадежностью канала и повторными передачами, будет следующим:

ii+ vt q, k = k vp k pcadr q, k qcadr q,k + vq k qcadr q,k. (1) ( ) ( ) ( ) ( ) ( ) ( ) () i=При расчетах примем lpacket = 1000 бит. Зависимости объемов издержек передаваемых данных для вероятностей битовой ошибки в 10–6, 10–3, 10–2 от числа кадров k, на которые разбивается пакет, представлены на рисунке.

При использовании каналов связи с низкой вероятностью возникновения битовой ошибки минимизация издержек достигается при пересылке пакета без разбивки (количество кадров равно 1). В случае использования зашумленных каналов целесообразна сегментация пакета на кадры (для канала с вероятностью битовой ошибки в 10–3 — на 28 кадров, для канала с 10–2 — на 100 кадров).

, бит k t(10–2) t(10–6) t(10–3) Вариант сегментации определяется числом кадров k, на которые разбивается исходный пакет. Оптимальной считается сегментация, при которой объем издержек передаваемых данных минимален. Значение объема издержек определяется по формуле (1). Выигрыш от использования сегментации для зашумленных каналов, определяемый как разность объемов издержек передаваемых данных без применения и с применением сегментации, представлен в таблице.

Выигрыш в объеме издержек передаваемых данных в зависимости от числа кадров Вероятность бито- Оптимальная сег- Издержки без сег- Издержки с сегмен- Выигрыш в объеме вой ошибки ментация, кадров ментации, бит тацией, бит издержек, бит 10–3 28 1616 68 10–2 100 6011 240 Построенная модель показывает, что использование оптимальной сегментации позволяет значительно снизить издержки передаваемых данных, вызванные ненадежностью канала, что, в свою очередь, позволяет снизить суммарный объем данных, передаваемых по сети. Таким образом, используя данную модель, при неизменной скорости передачи можно добиться снижения среднего времени ожидания доставки сообщения и повышения пропускной способности сети.

ЛИТЕРАТУРА 1. Богатырев В. А Надежность и эффективность резервированных компьютерных сетей // Информационные технологии. 2006. № 9. С. 25—30.

2. Таненбаум Э. Компьютерные сети. СПб: Питер, 2003. 992 с.

Сборник трудов молодых ученых и сотрудников кафедры ВТ 46 КОМПЬЮТЕРНЫЕ СИСТЕМЫ И СЕТИ 3. Богатырев В. А., Евлахова А. В., Котельникова Е. Ю., Богатырев С. В., Осипов А. В.

Организация межмашинного обмена при резервировании магистралей // Науч.-техн. вестн.

СПбГУ ИТМО. 2011. Вып. 02(72). С. 171.

Сведения об авторах Осипов Андрей Владимирович — аспирант; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра вычислительной техники; E-mail: osipov-andrey@mail.ru Фролова Надежда Игоревна — студент; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра вычислительной техники; E-mail: frolova_nadezda@mail.ru Сборник трудов молодых ученых и сотрудников кафедры ВТ МОДЕЛИРОВАНИЕ КОМПЬЮТЕРНЫХ СИСТЕМ И СЕТЕЙ УДК 004.РАСЧЕТ ЦЕН ОПЦИОНОВ АЗИАТСКОГО ТИПА МЕТОДОМ МОНТЕ-КАРЛО М. В. Пономарев Раскрыто понятие «азиатский опцион» и рассмотрены основы ценообразования опционов, согласно модели Блэка—Шоулза. Описана реализация модели с помощью метода Монте-Карло на языках программирования MatLab и С++, приведены результаты тестирования.

Ключевые слова: азиатский опцион, метод Монте-Карло, С++.

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 14 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.