МЕТОД ОБЕСПЕЧЕНИЯ ВРЕМЕННЫХ ПАРАМЕТРОВ КАЧЕСТВА ОБСЛУЖИВАНИЯ В РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

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

Ключовi слова:реконфиуровш обчислювальш системи, ятсть обслуговування, накладн видатки реконф^

гураци, програмовн логiчнi ттегральн схеми (ПЛ1С) □-□

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

интегральные схемы (ПЛИС) -□ □UDC 004.27

[DPI: 10.15587/1729-4061.2016.81003|

THE METHOD FOR PROVIDING QUALITY OF SERVICE TIME REQUIREMENTS IN RECONFIGURABLE COMPUTING SYSTEMS

Y. Kulakov

Doctor of Technical Sciences, Professor* E-mail: ya.kulakov@gmail.com I. Klymenko PhD, Associate Professor* E-mail: iklymenko@yandex.ua V. Tkachenko PhD, Associate Professor* E-mail: tkvalentina@yandex.ua О. Storozhuk Postgraduate student* E-mail: storozhuk.om@gmail.com *Department of Computer Engineering National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" Peremohy ave., 37, Kyiv, Ukraine, 03056

A paradigm of the solution of wide classes of tasks is the modern trends of development of reconfigurable computing systems, including the tasks that require strict time restrictions of run time, including real-time tasks. Reconfigurable computing systems are characterized by existence of constant structure and variable - as a set of computing nodes, whose structure can be rebuilt. According to this definition, reconfigurable systems are characterized by particular functional and hardware limitations caused by the use of reprogrammed components - FPGAs (field programmable gate arrays).

The processes that occur in dynamically reconfigurable computing systems and that stipulate problems with Quality of Service (QoS) [1], considering hardware constraints of FPGA, are the object of research in this work. Considering the prospect of using reconfigurable high-performance computing systems with increasing the efficiency of parallel computing, the quality of service provision is an actual problem for reconfigurable high-performance computing systems [1-3].

The evolution of techniques of partial dynamic reconfiguration on FPGAs [4-6] opens new opportunities for an

increase in efficiency of reconfigurable parallel computing systems due to implementation of dynamic reconfiguration of the computing structure, according to the requirements of executed applications. However, the traditional methods for providing QoS, developed for fixed computing systems arent effective for such systems, considering functional restrictions caused by delays in the process of dynamic creation of computing structure and spatial restrictions of FPGAs. Known methods of the accounting of these time delays can&t be effectively used within time restrictions of the run applications because of impossibility to evaluate their volume for implementation of the computation control optimization.

That is why there is a need of developing methods and means to ensure the required quality of service in reconfigurable computing systems with functional restrictions, that impact on the computation time.

Ensuring the quality of service in dynamically reconfigurable computing systems gains a certain flexibility by allow©

ing implementation of the most effective computing structure or reducing the computation time by accelerating the reconfiguration. There are many methods and means of acceleration of reconfiguration, which belongs to the type of "Best Effort", and mainly based on techniques of reducing the time overhead. The most known among them are reuse of resources [3, 4], prefetching of configurations [5], clustering of configurations [2] and hardware means for increasing the performance of interfaces [6]. All of them provide the maximum possible computing acceleration without any optimization of usage of the plane of the crystal of FPGA. The problem with excessive usage of computing resources of FPGA is resolved by means of delays of the execution of tasks, defragmentation, and unloading the less critical tasks, HW/SW approach [4]. This, in turn, decreases the level of QoS assurance by additional time expenses and failures in execution of tasks.

To ensure QoS, considering the required amount of used hardware resources, the effective solution was found and it is proposed for a well-known cluster computing system with multicore processors in nodes and reconfigurable structure shared among them [1, 8]. The involved reconfigurable structure consists of a set of similar fine-grained and coarsegrained modules, connected by a common communication network. The principle of reconfiguration is based on an extension of system instruction set to accelerate functional cores - Instruction Set Extensions (ISE) [9]. Herewith, each task depending on its computational complexity can be solved with different performance on various sets of equipment. The idea of the distribution of tasks consists of determination of the minimum required set of equipment, which will provide the required application&s execution time without excess equipment usage.

However, existence of predicated computing structure leads to necessity to bring the tasks to a determinant form, which is required by the system&s structure, and the reconfiguration is considered only at the level of connections commutation. The overhead reduction issue isn&t considered in this work, due to lack of reconfiguration of the computing structure.

The output computing application is a parallel program with mixed type of parallelism that is described by the programming model of M-tasks [10]. M-program is set by Macro Dataflow Graphs (MDG) [10] and macrograph tasks are placed in the vertices of it, and edges specify the relationship between vertices.

In this paper, the abstract concept of the hardware task is used, which in algorithms with the mixed type of parallelism corresponds to macrotasks that have some functional kernel of a computing algorithm synthesized in the digital circuit which in the algorithm mapping process is placed in the field of reconfigurable FPGA crystal. Each hardware task is associated with a work, that is defined by the amount of work, the appropriate certain top of a macrograph of the computing algorithm.

Let&s present the output program as macrograph GM=(VM, E), where VM - a set of vertices corresponding to macro tasks, and E is a set of edges that define the relationship between macro-tasks. Mapping by levels is a common method of mapping tasks to computing structure. Herewith each level of the graph is sequentially mapped on computer system structure [10].

Runtime of the computational program is defined as the sum of execution time of the longest sequence of tasks of each level and described as follows:

= 1 max {Tvt v = 1,Hk

where k = 1, w - the number of the level, w - the amount of levels of the computing algorithm, vk = 1,Hk - node number on the level k, Hk - the amount of nodes on the level k. Accordingly, the next ordered set of macrotasks is:

bg„ = {Tmxjk = 1,w},

where Tmax k - execution time of the longest task of the k-level, is the longest related sequence of tasks, which is the starting point for determining the total execution time of the program.

The runtime constraint is the time limit, set on the basis of certain external factors such as initial requirements of QoS of the application.

In this paper, the problem of time restrictions allocation among the sequences of executed tasks of the computational algorithm is resolved, to ensure execution of the algorithm in the dedicated time, efficient use of the FPGA resources and to reduce the number of tasks execution failures.

The structure of the dynamically reconfigurable computing system was designed, investigated and described in detail by the authors in the previous paper [7, 11, 12].

The purpose of this work is to improve the efficiency of reconfigurable computing systems, during the implementation of applications that put restrictions to the execution time.

To achieve the goal, the following tasks were set:

- to develop a means of improving the computation control process control in reconfigurable systems by assessment of unproductive time with regard to hardware limitations in FPGA while mapping computational algorithms to reconfigurable computing structure;

- to develop a method for providing requested quality of service in reconfigurable computing systems for applications that put restrictions to the execution time;

- to evaluate conditions of effective use of the offered facilities within the functional and hardware limitations of the reconfigurable computer system.

The positive effect from hardware acceleration of the computing process in reconfigurable computing systems is measured by the following index of performance acceleration [1, 8]:

where TSw - time required for computing the i-task on the processor kernel, THw - time required for computing the i-task by means of hardware (i = 1,n, where n is the number of tasks in sequence (1), to be performed (n=w)).

To determine the time constraints during solving parallel M-programs, presented in the parallel form graph of

the algorithm, let&s substantiate the possibility of using the well-known method [1], designed to determine the time constraints during solving of interrelated tasks in a multitasking mode. The method is based on using acceleration performance index (2) and assumption, that the overall time should be divided proportionally by the expected time of executing each task to determine the required amount of hardware to meet time constraints required by the application. Based on the stated above, we will present the well-known relation [1] in accordance with the problem statement of this paper:

TCounti X

appropriate configuration of appropriate hardware i-task on the fabric area of the reconfigurable computing module. Then, according to the equation (2), the performance acceleration index, which we will define as the factor of acceleration, equals

p ^sw,. iT

To prove the truth of the expression (3) and to receive the proportion between the main parameters, the geometric interpretation is shown (Fig. 1).

The diagram in Fig. 1 shows the total computational

time with software ^ SW j and computational time with i i n

hardware acceleration TTotal TCount ¡, KAv - averaging

where TqoS - overall time constraints of the program, factor, TAv i and ^ T S

computation time of the i-task

TqoS i - time constraints, calculated for each i-task to be performed, based on time requirements TqoS, TCount - expected time of the i-task performance, pi - productivity acceleration, calculated by the formula (2).

Define, that the computational time of some i-task using hardware resources is equal to TCount i=TRconf i+THw i, where TRconf i - reconfiguration time, spent directly on placing the

and the total computation time, respectively, calculated on the basis of averages. Line (I) shows the distribution of time intervals for the expected computation time parameters of tasks, line (II) - for the averaged parameters, line (III) -depict the process of correcting time intervals taking into account the parameters of quality of service QoS.

Fig. 1. Dependency of the execution time of the tasks on the performance acceleration index

The diagram in Fig. 1 shows that the total computation time with software and the total computation time with hardware acceleration, as well as all appropriate intervals that define each task in sequence of computations are in a proportional relation to the average acceleration factor pAv:

I TSW i i=1_

I TCount i

_ 1 SW i

i = (1,n) = Pav ,

-= TCounti XPa

Time intervals, obtained using the average acceleration factor, require correction over the deviation from the average value, which we will define as the averaging factor. The averaging factor is calculated by the following formula:

Kav i = , n ^

if PTi = "T. Accordingly,

pt = T SW i pi = 1 SW i

T ■ i t

If T&swi and T^SWi

are initial time parameters, corresponding to the input time value TSw i, where the index (t) represents the computational acceleration and (i) - the deceleration, its relation to the desired task execution time on the hardware will determine the acceleration factor value, according to the equation (4), and the acceleration factor value will determine the acceleration (if pi>1) or the deceleration (if pi<1) of the computational process. Then the equation (5) is appropriate for cases of computation acceleration so as for cases of deceleration. Based on the equation (5), we will obtain the dependence of the task runtime on the performance acceleration factor:

T = T v i=1

I TSWi Ip i

if Pi =—=P; i =

is average acceleration factor. The diagram (Fig. 1) shows, that if the acceleration factor of the i-task of the sequence pi is higher than the average acceleration factor pAv (KAv>1), this time needs to be corrected towards increase, and vice versa, if the acceleration factor of the i-task of the sequence pi is less than the average acceleration factor pAv (KAv<1), this time requires a correction towards decrease.

Thus, after carrying out correction, we get initial values of computational time without acceleration: the total 4. 1. Formalization of the modified method of determining the time intervals of tasks under time constraints required by QoS

The initial parameter for solving tasks of providing required time limits is an overall time-limit TqoS of the calculation algorithm, which is imposed by certain external factors. The initial parameters of the system are time parameters of each task TSw i, TCount i and values of performance acceleration factors calculated in the equation (4).

The time constraints imposing requires providing certain acceleration from executed tasks pQoS i, i. e. the execution time of each task from the tasks sequence is imposed by the following restrictions:

for each task - T SW i = TAv i xKAv i.

Based on foregoing, we define the following dependence of the execution time of the task on its acceleration factor:

T = T x1 SW i _ 1 Count i ^

I TCounti Ip i

= TCounti XpAv X i = TCounti Xpi,

T < T = sw i

Count i — J-QoS i _

in case of total computation acceleration, i. e.

-> 1,

To solve the task considering restrictions, we will calculate the value TqoS i according to the equation (6). From the previous studies it comes out that

according to the equation (4), it proves the validity of the equation (3) for the initial settings described above.

The following dependencies between the main computation parameters can be obtained from the diagram (Fig. 1):

T Count i = T SW i Xp i =

T = T X i=1

I TQoS i

I TSW i IPQoS i

i=1 V i=1 y

Thus, the expression is as follows:

TQoS i= T i X

TQoS PQoS i

- XT~n "

E TCount i EPQoS i

i=l V i=1

et sw i et i xPa

PQoS ="

-> T SW i = T i XP

tqos i = ^ = t , x

QoS Correct

then, the corrected value of the average acceleration, re quired by the time constraints equals

E Tt T Z-i sw i

P = T QoS X i=i

P QoS = n X E TCount i E TC

Comparing with the well-known method [4], the obtained expression considers a deviation, which is brought by the assumption that the given time limit TqoS is the average amount of time, and the acceleration factor, required by constraints, is the average acceleration factor. In this case, the following decision would be right:

The final equation for the calculations is as follows:

TQoS i= T i X

E TCount i E Tc

Execution of time constraints in general, is given by the equation:

T < T

Count i — J-QoS i(9)

In case of the ordered sequence of tasks and to address goals of this article, computations should be deprived of deviations. Geometric interpretation (Fig. 1) shows that the total computational time correction to the average value is equal to the total time value correction in the opposite direction. In case of preserving factors of deviation from the average before computations, it would be advisable to adjust the output time TqoS to the following magnitude, in order to bring the time to the average value:

Geometric interpretation of performed calculations is shown in Fig. 2.

Based on the above evidence, calculations and final equations (8) and (9) we can determine the following conditions for constraints execution:

process is less than 1 (pCp<1, E TSW i <E Ti) that is when

the overall computational process slows down (Fig. 1, 2) are not considered. Processor cores can execute such algorithms.

- maximum index of deviation towards a computation acceleration requirement:

dt = max(KtAv i |v(i = U, Pi > Pav ));

Fig. 2. Determination of the boundaries of the rational use of the proposed method

- maximum index of deviation towards a computation deceleration requirement:

^ = max(Kv i |v(i = û, Pi <Pav)).

In general, the maximum factor of deviation from the average value is defined as follows:

fl^max^ |v(i = 1n)),

Pmax = Pqos |(«> 1), Pmin = Pqos |(«< 1)> where pQoS is calculated according to the equation (8).

Time constraints execution conditions

Application settings Task settings Comment

Pmax > PQoS > P Av Pmax ^ PAv K Av i> 1 Pi > PAv Fit (acceleration of tasks is more than the average)

K Av i< 1 Pi < PAv Do not fit (acceleration of tasks is less than the average)

Pmax < PQoS >Pï Av For all tasks None of the tasks fit into constraints

Pmin < PqoS < P Av PQoS > 1 Pmin ^ Pav K Av i> 1 Pi > PAv Fit (acceleration of tasks is more than the average)

K Av i< 1 Pi < PAv Do not fit (acceleration of tasks is less than the average)

Pmin > PqoS > 1 For all tasks All tasks fit into the constraints

Therefore, based on the demanded QoS time constraints, the proposed modified method of determination of the tasks time is as follows:

- time constraint correction to the average value is performed;

- average time constraint distribution is performed proportionally to the average performance acceleration, getting the average intervals restrictions;

- correction of the averaged intervals towards an opposite direction of the averaging factor of each task is performed.

The proposed modified method for determination of tasks runtime and previously defined attributes of providing time requirements (Table 1) are used to implement the method for providing time requirements of QoS, consisting of the following stages:

Step 1. Determinate the rational boundary of providing timing conditions (10):

Pav > 1

Pmax > PqoS >1.

Step 2. Delete the sets of tasks D (Ti e D, if TRconf i = max) -the tasks which time cannot be reduced, in particular, the tasks of the first level of the parallel form graph from the sequence of tasks B (1):

Tvi eD, if Tvi = max{Tvi v1 = 1,H1},

It is advisable to introduce flexible limits for the maximum factor of deviation from the average value, which can be defined as follows:

tqos = tqos -£(Ti |vTi e D).

For this purpose, it is possible to use the standard deviation index 8, which is a measure of spreading the values of their average rates. The tasks, which acceleration of productivity approaches the values 38 (pj ^ 38), significantly affect the uniformity of time constraints distribution and it will lead, from the practical side of implementation, to excessive actions to minimize the time of task execution, and, as a consequence, to the excessive use of hardware and software resources of the system.

It is possible to form the following permissible boundaries of the specified time constraint, which are based on defined conditions and determine the case for rational usage of the proposed method:

PAv >1

Pmax > PQoS >1,

Pmax ^Pop , Pmil

Step 3. Ensure conditions fulfillment Pmax ^Pqos. Step 4. Calculate time constraints for tasks that remain in the sequence (8):

TQoS i = T i x

I T Count i I T Count i XPA

V(Ti ¿D).

Step 5. Determinate the concept of reducing the execution time for tasks that do not fit into the time limits, based on the maximum or partial reduction of the reconfiguration time parameter:

Pi V(TCounti < TQoS i) =

TRconf i + THW i

TRconf i ^ min, TCount i ^ THW i

Theoretical research of the effect of application of the proposed method of time distribution is completed. Randomly synthesized sequences of tasks were researched. The characteristics of hardware functional cores, which were synthesized on FPGA Cyclone II Altera, were taken as their timing parameters. Diagrams (Fig. 3) show that inversely proportional correction (Tqos mod) of averaged time intervals (Tqos av) provides additional time resources to the critical tasks, which have high acceleration factor (higher than average). The graph shows that Tasks (2, 5-6) are no longer critical, because they got extra runtime. It can be seen that the Task 5, whose acceleration factor is slightly lower than average, also got enough runtime.

This distribution is effective on condition of uniform deviation of the acceleration factor from the average value. Otherwise, we can see excessive allocation of time for the tasks, which have acceleration factor higher than the average value. Further, in the sequence of tasks there may be the tasks, the runtime of which cannot be reduced, i.e. the tasks of the first level of the parallel form of the algorithm. Therefore, during the allocation, these tasks should be defined as those, which cannot be effectively executed with the usage of the proposed method, as was described above. These tasks should be deleted from a general sequence of proposed method applying and required execution time should be given to them.

The software emulator of reconfigurable computing systems and software model of the implementation of the proposed method [12] were designed for simulation of the proposed method for providing time requirements of QoS for reconfigurable computing systems. Efficiency of the software model is proved by modeling the functional elements of the system with timing characteristics, maximally approached to the real. Timing characteristics of functional blocks of tasks, module components and functional processes of a computing system are obtained from the developed models, which were synthesized by the usage of Verilog language and implemented on FPGA Cyclone II Altera.

The research is conducted for a set of applications presented as parallel form graphs of the algorithms. Based on conducted experiments, comparative dependences of execution time for different mechanisms of accelerating the computational process for algorithms with different number of similar tasks are obtained (Fig. 4).

■ Standard reconfiguration

■ Proposed method ■Runtime limit

■ Intensive acceleration Hardware computation

Fig. 4. Analysis of the reconfiguration time

The diagram Fig. 4 shows that the reconfigurable computations performed by means of standard reconfiguration sequence require significant time of execution in case with no acceleration due to a significant advantage of reconfiguration time over execution time of the task. Herewith, the computation time does not depend on the type of tasks performed. Removing similar tasks& reloading leads to intensive acceleration. Efficient method of intensive acceleration was proposed and described by the authors in the previous paper [12]. The graph shows that the minimum computation time is achieved provided that the width of the MDG graph corresponds to spatial parameters of the reconfigurable FPGA environment [11]. With the increasing number of similar tasks, it is necessary to introduce additional tools for loading of the active tasks. It requires extra time as shown in Fig. 4. The proposed method allows optimizing the proposed technology of intensive acceleration [12]. The diagram demonstrates that the proposed method allows to stay within time constraints, required by the application for cases with a large number of similar tasks.

Fig. 3. Providing additional runtime for critical tasks

^—Intensive accelerations ^—Proposed method

Fig. 5. Analysis of the acceleration factor

According to the analysis of the acceleration factor, the mechanism of resources reuse provides an intensive acceleration of reconfiguration with increasing the number of tasks types to the amount that is commensurate with the width of the parallel form graph. Increase in intensity of acceleration of reconfiguration on average by 63 % is achieved, if the

reconfigured area is commensurate with the width of the parallel form graph and there are many similar tasks. Herewith, there is a sharp decrease in the intensity of acceleration of reconfiguration, on average by 85 % during the process of overcoming the spatial constraints of FPGA.

The proposed method for ensuring time constraints reduces the intensity of the impact of spatial constraints on the computation speed, in this case approximately by 10 %. However, this measure depends on the defined amount of reconfiguration overhead with criteria of providing time and hardware restrictions of the reconfigurable computing systems.

From a practical point of view, we can interpret the proposed method of determining time-limit intervals as follows. The correction of the averaged periods is performed by allocation of an additional time of execution to the tasks, which have high acceleration factor (higher than average), using tasks with low acceleration factor (lower than average). Considering the acceleration factor as a measure of effective hardware task implementation, tasks with high acceleration factor can be effectively solved by the means of the standard sequence of the reconfiguration process. Otherwise, it is necessary to introduce additional means of tasks implementation acceleration, particularly, by reducing reconfiguration time.

The use of the service quality support method allows to define such sequence of tasks for which the target architecture of the computing system is effective and the use of additional mechanisms of an acceleration of reconfiguration and reduction of overhead costs [2-5, 12] doesn&t lead to an acceleration of computation within the exposed temporal requirements. Resolving of these tasks by standard utilities of reconfigurable computation reduces excess use of the hardware and hardware-software resources of the reconfigurable computing system. The use of the offered method allows to reduce the influence of space constraints for the period of reconfiguration and to reduce the quantity of deviations of execution of tasks in case of dynamic mapping of the flow of tasks.

Modification of the quality provision method allows to determine a sequence of tasks execution within implementation of the service quality support method in the reconfigurable computing systems. The paper mathematically proved the increase in accuracy of calculations, in comparison with the known method. Mathematical reasons for the offered means prove the reliability of the use of the offered method and the method of its implementation for computing algorithms with the mixed type of parallelism provided by graphs of parallel form graphs of the algorithm.

The offered method allows to provide a wide class of tasks with effective target computing structure for achievement of the necessary quality level of service, and also to reduce the quantity of failures in case of distribution of a flow of tasks, arriving dynamically.

The offered method can be used for an increase in efficiency of high-performance reconfigurable computing systems in case of the solution of tasks of control of different technical and technological processes and implementation of multivariate computation in complex information systems.

References

-□ □Описано методику та результати дослиджен-ня впливу форми напруги живлення рентгетвського випромтювача на загальну дозу опромтення пащен-тiв шд час виконання медичних обстежень. Надано результати експериментальних вимiрiв, описано алгоритм розрахунку дози опромтення, проведено порiв-няльний аналiз дозового навантаження на пацiентiв при використанн рiзних видiв джерел живлення та аналiз ефективностi модернiзацii ^нуючого рентгетвського обладнання

Ключовi слова: чисельне моделювання, еквiвалент-на доза опромтення, медичнрентгетвсьт обстеження, джерела живлення

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

исследования, источники питания -□ □UDC 004.94 : 621.386.12

|doi: 10.15587/1729-4061.2016.81305|

EXPLORING DEPENDENCE OF THE PATINTS& RADIATION DOSE ON THE FORM OF POWER SUPPLY VOLTAGE OF X-RAY

Senior Lecturer* E-mail: iec-lab@karazin.ua M. Malakhova

Postgraduate student* E-mail: maryna.malakhova88@gmail.com *Department of Electronics and Control Systems V. N. Karazin Kharkiv National University Svobody sq., 4, Kharkiv, Ukraine, 61022

the diagnoses that require serious medical intervention is In modern medicine, one of the most common and im- performed using X-ray images, results of roentgenoscopy and portant methods of diagnosis is the X-ray study. According X-ray tomography. X-ray images are the main tool for the