А О Мельник - Структура та характеристики векторної пам'яті з впорядкованим доступом - страница 1

Страницы:
1  2 

УДК 004.33

А.О. Мельник1, Н.М. Ліщина2

Національний університет "Львівська політехніка", кафедра електронно-обчислювальних машин 2Луцький інститут розвитку людини університету "Україна",

кафедра комп'ютерних технологій

 

СТРУКТУРА ТА ХАРАКТЕРИСТИКИ ВЕКТОРНОЇ ПАМ'ЯТІ З ВПОРЯДКОВАНИМ ДОСТУПОМ НА ОСНОВІ НАЛАШТОВУВАНОЇ СОРТУВАЛЬНОЇ МЕРЕЖІ

© Мельник А.О., Ліщина Н.М., 2011

Запропоновано основні типи структур пам'яті з впорядкованим доступом на основі налаштовуваної сортувальної мережі. Оцінено час налаштування цих типів пам'яті з впорядкованим доступом, час записування та зчитування вектора даних, а також затрат обладнання на реалізацію розроблених типів пам'яті з впорядкованим доступом.

Ключові слова: пам'ять, впорядкований доступ, пам'ять з впорядкованим доступом.

 

The basic types of ordered access memory structures based on customizable sorting network are proposed. The estimation of customizing time of these memory types, writing and reading time and cost of equipment to implement the developed types of ordered access memory is performed.

Key words: memory, ordered access, ordered access memory.

 

Вступ

Пам'ять використовують для зберігання інформації та забезпечення обміну нею між пристроями комп'ютера. Вона має визначальний вплив на технічні характеристики комп'ютера. Тому існує потреба в покращенні технічних характеристик та функціональних можливостей пам'яті.

Огляд літературних джерел

Серед сучасних напрямів покращення характеристик пам'яті передусім потрібно відзначити роботи з забезпечення паралельного доступу до даних в пам'яті та виконання операцій впорядкування векторних, які зберігаються в пам'яті [1,2]. Такі функції повною мірою забезпечує лише пам'ять з впорядкованим доступом (ПВД), в якій здійснюється доступ до даних у програмно встановленому порядку, тобто індекс, який надходить у пам'ять разом з даним, або під час його зчитування, вказує місце даного у вихідному масиві. У деяких роботах останніх років були вирішені проблеми розроблення методів побудови цієї пам' яті, принципів її структурної організації та визначення її місця серед інших типів пам'яті. Зокрема були досліджені проблеми організації пам' яті, розроблені критерії порівняння різних типів пам' яті та показано, що ПВД є найефективнішою для роботи з масивами даних, а також були розроблені методи побудови та структурної організації пам'яті з впорядкованим доступом на основі сортувальної мережі [3-5]. У роботі [6] запропоновано алгоритми впорядкування даних за значенням їх індексів, інтерфейс паралельної пам'яті з впорядкованим доступом та розроблено структуру паралельної пам'яті з впорядкованим доступом на основі налаштовуваної сортувальної мережі (ПВДН). Проведено дослідження структури та технічних характеристик векторної ПВДН та її порівняння з іншими типами пам'яті. У роботі [7] запропоновано метод побудови векторної пам'яті з впорядкованим доступом на основі налаштовуваної сортувальної мережі.

 

 

89Постановка задачі

Хоча протягом останніх років ПВДН була доволі ґрунтовно досліджена, існує низка проблемних питань її побудови.

Так, часто виникає потреба в простіших її варіантах, коли впорядковується не матриця, а вектор даних, або з виходу зчитується не матриця, а вектор даних. При цьому можливі різні варіанти надходження вхідних даних та зчитування вихідних даних. Перерахуємо ці варіанти:

  варіант "рядок - рядок" - до ПВДН надходить рядок вхідних данихIID0, ID1, ... IDl-1 І


(1)та зчитується рядок вихідних даних|OD0, OD1, ... ODn-1 |;


(2)•  варіант "рядок - стовпець" - до ПВДН надходить рядок вхідних даних (1) та зчитується стовпець вихідних даних

OD0 OD1ODm-1


(3)   варіант "рядок - матриця" - до ПВДН надходить рядок вхідних даних (1) та зчитується матриця вихідних даних

' ODO,    OD1, ... ODm-1 ODm,   ODm+1, ... OD2m-lODn-m, ODn-m+1, ... ODn-1

варіант "стовпець - рядок" - до ПВДН надходить стовпець вхідних даних

IDO ID1

IDk-1


(4)(5)

та зчитується рядок вихідних даних (2);

       варіант "стовпець - стовпець" - до ПВДН надходить стовпець вхідних даних (5) та зчитується стовпець вихідних даних (3);

       варіант "матриця - рядок" - до ПВДН надходить матриця вхідних даних

, (6)

та зчитується рядок вихідних даних;

       варіант "стовпець - матриця" - до ПВДН надходить стовпець вхідних даних (5) та зчитується матриця вихідних даних (4);

       варіант "матриця - стовпець" - до ПВДН надходить матриця вхідних даних (6) та зчитується стовпець вихідних даних (2).

Базуючись на ньому, розглянемо основні варіанти ПВДН з позиції їх структурної організації та технічних характеристик, з врахуванням перерахованих вище варіантів надходження вхідних даних та зчитування вихідних даних.

 

 

901. Структурна організація векторної пам'яті з впорядкованим доступом на основі налаштовуваної сортувальної мережі

1.1. ПВДН типу "рядок - рядок"

Оскільки дані надходять у вигляді рядка, їх індекси відразу можна впорядкувати в НСМ, після чого впорядкувати дані та записати до ПВДН. При цьому індекси до пам'яті записувати не потрібно. Структура ПВДН даного типу показана на рис.іа.

У режимі налаштування на налаштовуваній сортувальній мережі НСМ здійснюється впоряд­кування індексів у векторі індексів вхідних даних IIID0, IID1, ... IIDl-1 |, тобто формування вектора | SV0, SV1, ... SVl-1 | , відповідно до якого у режимі впорядкування здійснюється перестановка даних у векторі вхідних даних I ID0, ID1, . IDl-1 I , після чого вони записуються до регістрів Рг0-Ргп-1 сигналом запису W. Час запису даних до ПВДН визначається сумарним часом виконання операцій впорядкування індексів та перестановки даних в сортувальній мережі. Вектор вихідних даних | OD0, OD1, ... ODn-1 |зчитується з регістрів Рг0-Ргп-1 сигналом зчитування R.

1.2. ПВДН типу "рядок - стовпець"

Нехай до ПВДН записують рядок вхідних даних (1) в режимі впорядкування паралельно після надходження вектора їх індексів

| IID0, IID1, ... IIDl-1 | (6)

в режимі налаштування, тобто k=1, l=L, і на вихід ПВДН паралельно зчитують стовпець вихідних даних (3), тобто m=M, n=1. Отже, в ПВДН рядок перетвориться в стовпець. В цьому випадку до ПВДН за один такт сигналом W записуються l даних, а потім за m тактів зчитуються m даних (у кожному такті одне дане), причому m=l. Така ПВДН може бути реалізована в кількох варіантах. Один із варіантів -побудова ПВДН на базі схеми, показаної на рис.1а, якщо її виходи об'єднати спільною шиною та додати лічильник Л, який підраховує сигнали зчитування R та вказує з якого номера вихідного регістра на якому номері сигналу зчитування R дозволяється зчитування (рис. 1, б).

1.3. ПВДН типу "рядок - матриця"

Нехай до ПВДН записують рядок вхідних даних (1) в режимі впорядкування паралельно після надходження вектора їх індексів (6), тобто k=1, l=L, і на вихід ПВДН зчитують вектор вихідних даних (3) у вигляді матриці групами по m даних (4).

Отже, в цій ПВДН рядок перетвориться в матрицю, тобто m=M, n=N. У цьому разі схема ПВДН збігається з показаною на рис. 1, б, з тією відмінністю, що із вихідних регістрів одночасно зчитують m чисел (рис. 2, а). Для цього вихідні регістри поділено на групи по m регістрів Рг0-Ргт-1, Ргт-Рг2т-1, ... Ргп-гп-Ргп-1 та виходи кожного i-го регістра, де i=(j)modm, j=0,1,...n об'єднані спільною шиною. Лічильник Л підраховує сигнали зчитування R та вказує, з якого номера вихідного регістра на якому номері сигналу зчитування R дозволяється зчитування.M ■ 1


 

i-i


I I DI° S1

D °      D 1

D

1    I   - I


i-i

НСМ

Рг 1

 

 

її


Рг

m-1


T

 

W

 

 

 

 

ROD

Рис. 1. Структура ПВДН типу "рядок - рядок" (а) та "рядок - стовпець " (б)

 

 

911.4. ПВДН типу "матриця - рядок"

Нехай до ПВДН записують вектор вхідних даних у вигляді матриці групами по k даних (6), які надходять після вектора своїх індексів

 

 

 

(8)тобто k=K, l=L, і на вихід ПВДН зчитують паралельно рядок вихідних даних (2), тобто m=1, n=N. При цьому L=N.

Структура ПВДН цього типу (рис. 2, б) містить згруповані по k регістрів вхідні регістри Рг0-Ргк-1, Ргк-Рг2к-1, ... Рг1-к-Рг1-1 для зберігання даних та індексів, до яких спочатку в режимі налаштування індекси, а пізніше в режимі впорядкування дані записують групами, після чого проводиться впорядкування даних за величиною їх індексів на налаштовуваній сортувальній мережі НСМ.

У режимі налаштування сигналом запису W індекси вхідних даних запишуться в відповідні регістри, причому місце запису індексів вказується сигналом з виходу лічильника Л, який формує сигнали дозволу запису. Цей лічильник спочатку перебуває в стані "0" та дозволяє запис першої групи індексів даних до регістрів Рг0-Ргк-1, після надходження першого сигналу запису W переходить в стан "1" та дозволяє запис другої групи індексів даних до регістрів Ргк-Рг2к-1, після надходження другого сигналу запису W переходить в стан "2" та дозволяє запис третьої групи індексів даних до регістрів Рг2к-Рг3к-1, і так до запису 1/к-ї групи індексів даних до регістрів Рг1-к-Рг1-1.

Пізніше вхідні дані в режимі впорядкування запишуться в відповідні регістри аналогічно як це було з їх індексами та впорядкуються у налаштовуваній сортувальній мережі НСМ та надійдуть на входи вентилів В0, В1... Вт-1. З виходів цих вентилів вихідні дані OD0, OD1, ODn-1 під час надходження сигналу зчитування R будуть подані на вихідну шину.I I D° SD1

Р°     D 1


I

dsI-1

D 1



Dk1

Mk-1

Л1W


да


да


itk-1


2k -1

 

Рг ° -


 

Л

 

 

Вихід н

шини


 

 

 

R


Dr SDDk

2k-1 . Dk


O1Рис. 2. Структура ПВДН типу "рядок - матриця" (а) та "матриця - рядок" (б).

 

 

 

 

 

1.5. 92ПВДН типу "стовпець - рядок"

Нехай до ПВДН записують стовпець вхідних даних (5) в режимі впорядкування послідовно після надходження стовпця індексів вхідних даних

SID0 SID1

SIDk-1

, (9) тобто k=K, 1=1, і на вихід ПВДН паралельно зчитують рядок вихідних даних (3), тобто m=1, n=N. При цьому K=N.

Структура ПВД цього типу (рис.За) містить вхідні регістри Рг0 - Ргк-1 для зберігання даних та індексів, до яких дані і індекси записують поодинці, тобто послідовно, а потім проводиться впоряд­кування даних за величиною їх індексів, використовуючи налаштовувану сортувальну мережу НСМ.

Сигналами запису W індекси вхідних даних в режимі налаштування запишуться в відповідні регістри, причому місце запису вказується сигналом з виходу лічильника Л, який формує сигнали дозволу запису. Цей лічильник спочатку перебуває в стані "0" та дозволяє запис індексів першого даного до регістра Рг0, після надходження першого сигналу запису W переходить в стан "1" та дозволяє записувати індекси другого даного до регістра Рг1, після надходження другого сигналу запису W переходить в стан "2" та дозволяє записувати індекси третього даного до регістра РгЗ і так до запису індексів k-го даного до регістра Ргк-1. Після цього сигналом T в тригерах налаштовуваної сортувальної мережі НСМ фіксується її стан для заданого вектора індексів.

Пізніше вхідні дані в режимі впорядкування запишуться в відповідні регістри аналогічно як це було з їх індексами та впорядкуються у налаштовуваній сортувальній мережі НСМ, та надійдуть на входи вентилів В0, В1... Вп-1. З виходів цих вентилів вихідні дані OD0, OD1, ODn-1 під час надходження сигналу зчитування R будуть подані на вихідну шину.

1.6. ПВДН типу "стовпець - матриця"

Нехай до ПВДН записують стовпець вхідних даних (4), які надходять послідовно в режимі впорядкування після послідовного надходження в режимі налаштування стовпця індексів вхідних даних (9), тобто k=K, 1=1, і на вихід ПВДН зчитують вектор вихідних даних (2) групами по m даних (4). Отже, в цій ПВДН рядок перетвориться в матрицю, тобто m=M, n=N. При цьому K=N.

Структура ПВДН цього типу (рис. З, б) містить вхідні регістри Рг0 - Ргк-1 для зберігання даних та індексів, до яких дані і індекси записують поодинці, тобто послідовно, а потім проводиться впорядку­вання даних за величиною їх індексів, використовуючи для налаштовувань сортувальну мережу НСМ.Да .


нРг 0


I

Рг

і

Страницы:
1  2 


Похожие статьи

А О Мельник - Автономна адаптивна система виявлення та відстеження порушників

А О Мельник - Апаратна реалізація циклів програмованих конфігурованих процесорів

А О Мельник - Теоретичні засади формування та реалізації механізму виявлення передумов світових економічних криз

А О Мельник - Реалізація програмних спеціалізованих процесорів

А О Мельник - Структура та характеристики векторної пам'яті з впорядкованим доступом