Электронный архив
Донецкого национального технического университета (г.Донецк)
Electronic archive of Donetsk national technical university (Donetsk)
 

eaDonNTU, Donetsk >
Научные труды ДонНТУ >
Серія: Інформатика, кібернетика та обчислювальна техніка >
Випуск 2 (18) >

Please use this identifier to cite or link to this item: http://ea.donntu.org/handle/123456789/29925

Title: Результативність евристичного алгоритму розміщення даних в КМПК з кеш-пам'яттю мікрокоманд
Other Titles: Результативность эвристического алгоритма размещения данных в КМУУ с кэш-памятью микрокоманд
Effectiveness of the heuristic algorithm of data allocation in CMCU with cache memory of microinstructions
Authors: Ніколаєнко, Д.В.
Николаенко, Д.В.
Nikolaienko, D.V.
Keywords: мікропрограмний пристрій керування
кеш-пам'ять
мікрокоманда
граф-схема алгоритму
оптимізація ймовірності кэш-влучень
евристичний алгоритм
керуюча пам'ять
микропрограммное устройство управления
кэш-память
микрокоманда
граф-схема алгоритма
оптимизация вероятности кэш-попаданий
эвристический алгоритм
управляющая память
microprogram control unit
cache memory
microinstruction
flowgraph
cache hits probability optimization
heuristic algorithm
control memory
Issue Date: 2013
Publisher: ДонНТУ
Citation: Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка : збірник статей. Вип.2 (18) / ДВНЗ "ДонНТУ" ; редкол.: О.Є. Башков (голов. ред.) та ін. - Донецьк : ДонНТУ, 2013.
Abstract: У роботі виконаний аналіз ефективності евристичного алгоритму оптимізації розміщення мікрокоманд в адресному просторі керуючої пам'яті, що дозволяє підвищити величину ймовірності кэш-влучень модуля кеш-пам'яті у складі композиційних мікропрограмних пристроїв керування з поділом кодів. На прикладі граф-схеми алгоритму середньої складності досліджені ефективності шести різних стратегій вибору першого операторного лінійного ланцюга при формуванні блоку керуючої пам'яті. Отримано значення приросту ймовірності кэш-влучень для різних розмірів рядка модуля кеш-пам'яті.
Description: Relevant scientific challenge is to expand the scope of digital systems. One way of solving this problem is to increase the performance of digital systems by increasing the speed control memory. Based on the previously proposed method for increasing the speed of compositional microprogram control units with codes division, which employs the composite structure of the microprogram control unit cache microinstructions, we analyzed the effectiveness of the heuristic optimization algorithm for allocating microinstructions in the control memory address space, which allows increasing the probability of cache hits of the cache memory module in compositional microprogram control devices with codes division. The factor, which determines the efficiency of cache memory and the whole structure, is cache hits probability ph, the value of which depends on the cache memory parameters and the characteristics of the implemented flowgraph of the control algorithm. For the experiments we made up two test flowgraphs of the algorithm. One of them contained non-elementary linear chains and the other contained elementary operational linear chains. Each flowgraph included 100 operational linear chains, each with 10 microinstructions. Thus, the number of microinstrictions in each flowgraph of the algorithm is 1000, which corresponds to the flowgraph of an algorithm of medium complexity. On the example of the flowgraph of such an algorithm we studied the effectiveness of six different strategies for selecting the first operator linear chain in the formation of a control memory unit. We obtained the values of cache hits probability increment for various sizes of cache memory module line. The aim is to study the effectiveness and feasibility of this heuristic algorithm application. As a result, we obtained numerical values of heuristic algorithm efficiency. The importance of the work is in the fact that heuristic algorithm application does not affect the control device structure. That is why the circuits of the devices designed with the use of the heuristic algorithm and without it differ from each other only by cache hits probability, and in 84% of cases the heuristic algorithm has advantages.
URI: http://ea.donntu.org/handle/123456789/29925
Appears in Collections:Випуск 2 (18)

Files in This Item:

File Description SizeFormat
Nikolaienko.pdf460.03 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.