Abstract
on master
thesis theme: “Development and research of compositional micro program control devices”
Introduction
Nowadays,
during development of electronics device, a lot of programmable LSIC, ROM, SPLD
and CPLD are used. This basis is used
in various computing devices and automatic control systems. This allows to improve such characteristics of devices as reliability,
speed, power consumption, size etc. But high complexity of this basis forces to
design efficient structures of developed devices and formal methods of their synthesis.
The
principle of micro-program control forms the basis of modern digital systems. This
principle supposes that the system includes a control automaton. This automaton
coordinates the operation of all blocks
of the system. Growth of complexity of the element basis demands the
development of new structures and algorithms for the synthesis of control
automata.
Control
automaton can be realized as a composition of hard logic automaton and
programmable logic automaton. Such automata were offered by A.A. Barkalov and
named as compositional micro-program control devices (CMCD). In CMCD the
minimal possible volume of control memory and maximal speed are obtained.
Usually
the control memory is realized as a read-only memory (ROM), which has low speed
relatively to other nodes of the circuit. In such case there is a problem of
increasing CMCD speed by decreasing the micro-command fetch time. One way of
solving this problem is introducing cache memory into the structure of CMCD. This memory is realized as a high-speed
static memory and it is intended for temporary storage of a micro-command which
was used during some the last tact of device operation.
The
master’s thesis is devoted to the solution a topical scientific task of
developing CMCD structures and methods of their efficiency estimation. This
task is oriented to increasing circuit speed when CCMD is realized in the basis
of programmable LSIC.
Aims and
tasks of research
The
aim of the work is to increase of CMCD speed by
decreasing the average time of access to control memory.
The main tasks of the research. To achieve the
aim of research it is necessary:
1.
To perform analysis of the main architectures of cache memory which are
used in modern computing devices; modern element basis which is used in
synthesis of micro-program control devices;
modern CMCD optimization methods.
2.
To develop structural and functional CMCD diagrams with direct mapped
cache and fully associative cache.
3.
To develop the methods of cache
memory efficiency estimation in CMCD.
4.
To explore the developed CMCD cache memory structures in order to define
the area of their efficient application.
New
scientific results
The
scientific results are defined as follows:
1.
Development of structures and functional diagrams of CMCD with cache
memory, which have higher speed compared to the currently available.
2.
Development of analytical methods for determining probability of cache
hits for CMCD with cache memory using Random algorithm.
3.
Analytical efficiency of depends of using cache memory in CMCD depends
on control algorithm flow chart, type of cache memory and element basis.
Practical Importance
The
practical significance of the work consists in the development of an imitation
analytical software model, which realizes analytical methods of determining
probability of cache-hits for CMCD with direct mapped and fully associative
cache according to flow chart, and in the determining efficient cache memory
application areas in CCMD. The results obtained in the work were realized as
methods of CMCD with better characteristics of synthesis.
Review of the
state of research and developments
In
the PhD thesis of R.M. Babakov (scientific supervisor is S.A. Kovalyov) the
CCMD logical circuit structures with cache memory and the methods of efficiency
estimation for their realizations in LSIS programmable basis were developed.
During
the research the following tasks were solved:
1.
The main cache memory architectures which are used in modern computing devices;
modern element bases which is used in synthesis of micro-program control device
and modern CMCD optimization methods were analyzed.
2.
The structural and functional CMCD diagrams with direct mapped cache and
fully associative cache were developed.
3.
The methods of analytical definition of cache-hit probability for a given
flow-chart and characteristics of cache memory were developed. The methods are
elaborated for direct mapped cache and fully associative cache.
4.
Analytical estimation of speed increasing using cache memory in CMCD.
Using cache memory in CMCD leads, in common case, to increasing of middle speed of device
circuit in 2-5 times and higher depending on element bases characteristic and
structure of realizing algorithm of control. The cache-hits probability
definition methods according to flow chart, which were offered in the work,
allows to get result, in common case, in several times faster, than using
experimental methods.
5.
The algorithm of choosing of optimal cache memory characteristic is
elaborate. It allows define the amount of strings and the size of cache memory
string for given algorithm. It lets to obtain the maximum cache-hits possibly
probability and increasing of device speed. Given algorithm can be used in synthesis
of CMCD circuits with cache memory, which have maximum possible speed with
given control algorithm and allowed volume of cache memory.
The list of
undecided problems and questions
Cache
memory is used for keeping of micro-command, which can form in CMCD in the
nearest time. Statistical analyze of modern computers working shows that
approximately 90% of all data which is inquired by calculate device usually
accommodate in cache memory. This value names as coefficient or probability
of cache memory [1, 2]. For definition of cache memory probability
value two ways can be offered: experimental and analytical.
Experimental
method of cache-hits probability definition consists of
program model of CMCD with cache memory with the goal of statistical collection
of information about cache-hits and cache-miss amount during execution of
algorithm for a long time. The advantage of experimental methods is limit
accuracy which depends from experiment repeating number. The time which is
necessary for long time algorithm execution can depend from some logical
condition probability values, because some areas of algorithm can form long
cycles. With increasing of algorithm difficulty it’s modeling time increase in
non proportional dependence from amount of micro-command proceeds between them.
Analytical
method lets to get exact value of cache hits probability.
All micro-command and algorithm connection take into account. The time of
calculating depends only on number of micro-commands and connections between
them, and is not in dependence from logical condition proceeds probability
values.
In
hard CMCD inside structure orientation for realization of concrete algorithm
the
necessity of exact analytical cache hits probability method elaboration
appears, which allows to choose the most optimal according to high speed
characteristics point cache memory in CMCD
with some increasing of device cost.
As
it was tacking before, nowadays analytical methods of estimation speed
increasing using direct mapped and fully associative cache in CMCD. In fully
associative cache various algorithms of replacement such as LRU, Random, Timer,
can be used.
LRU
- replacement the string which has the least value in the tact apply register
when cache-hit.
Random
- replacement the string choosing in randomly.
Timer
- replacement the string with the maximal time from the moment of applying.
In
the dissertation work of R. M. Babakov only analytical method of estimation speed
increasing using fully associative cache with algorithm of replacement LRU was
developed. Random and Timer algorithms are not exploration.
Current and
plan results
Current
result of master stadium work is program model, which realized experiment
method of estimation speed increasing definition using fully associative with
Random algorithm of replacement. It is planed to get results of analytical
method if exploration of fully associative cache with Random algorithm of
replacement.
Conclusion
In
master stadium work the decision of actual science task is given. This task is
important for digital automation and calculation technique industry. It consists
in elaboration of new CMCD logical circuit structure with cache memory and
methods of effectiveness estimation in programmable LSIC bases realization.
Source
1.
Hill Mark Donald. Accepts of Cache Memory and
Instruction Buffer Performance. – Ph. D. Dissertation, Computer Science Division
(EECS),
2.
Smith A.J. Second Bibliography on Cache Memories // Computer
Architecture News, 19(4):154-182, June 1991.