• Không có kết quả nào được tìm thấy

Thư viện số Văn Lang: Journal of King Saud University - Computer and Information Sciences, Volume 15

Nguyễn Gia Hào

Academic year: 2023

Chia sẻ "Thư viện số Văn Lang: Journal of King Saud University - Computer and Information Sciences, Volume 15"


Loading.... (view fulltext now)

Văn bản

The basic concept of the DBS technique depends on dividing the entire matrix into a number of vertical segments. In this section, we give a brief description of the proposed tool used to support the DBS technique. The basic concept of the DBS technique depends on dividing the entire matrix into a number of K vertical segments.

To obtain the upper triangular form of the matrix, the DBS technique transforms each vertical segment (denoted by VSl; 1d l dK) into Segmental Upper Triangular (SUT) form. VSl(x,y): represents the value of the element VSl in row x and column y of the matrix QT;. Develop the full matrix QT (NuN) from the RG of the desired model (see Figure 2.a).

In the next section, we discuss several implementation issues of the DBS technique.

Implementation of the DBS Technique

Implementation of the reduction and history analysis

To avoid handling the entire rows of the matrix, we used a modified version of the SRGR technique. The MSRGR technique helps us to reduce the row sections to its Segmental Upper Triangular Row (SUTR) form. The definition of the SUTR form follows from the fact that each segment VSl is composed of a set of N row segments (i.e. VSl { rowil; 0d i

Algorithm: Re-implementation processes of step 4 of the DBS technique (explained in Section 3) according to the MSRGR technique described above. 3 shows the execution processes of the combined RA and HA for VS2 of the matrix shown in FIG. i) Apply the history analysis of rowil. ii) Transform the rowil into its SUTR form using reduction analysis. iii) Transfer rowil from the reduction buffer to the RAM as shown in fig. iv) Record all computational operations performed during the RA of rowil in a part of the history list (denoted by PHLil), see fig. It is interesting to note that not all the regions in the row parts are exposed to RA.

Let the upper diagonal region be the region that exists above the diagonal path through each vertical segment. If we divide the vertical segment VSl into these three regions, the row parts of the upper diagonal region (rowil; 0 d i d Colbl) will not undergo the reduction analysis. On the other hand, the row parts of the diagonal region (rowil; Colbl < i d Colel) and the lower diagonal region (rowil; i > . Colel) will undergo reduction analysis.

3.c, 3.d and 3.e, we describe the application processes of the RA on the row sections: row12, row32 and row52, as examples of these regions. The result of the RA of the row sections of the lower diagonal region is the complete elimination of its elements as shown in Fig. On the other hand, the result of the RA of the row sections of the diagonal area is the partial elimination of its elements as in Fig.

Estimation of the suitable number of vertical segments

When we increase the K parameter, the final sizes of the vertical segments after the transformation decrease. We used the following lemma to estimate the number of nonzero elements in any column j (denoted by Colj). Simulate the effect of the GE method on the elements of the QT matrix shown in Fig.

To simulate the effect of the GE method on the elements of matrix QT shown in Fig. 4.b, we must therefore monitor the elimination operations that the GE method performs on the elements of matrix QT in each of its N steps. Suppose we first monitor the second step performed by the GE method on the elements of matrix QT (ie, eliminating non-zero elements that exist in Col1 below the diagonal element e11).

The elements of the matrices Q{{qij}NuN (or QT) arising from systems modeled by the Petri net (PN) theory exist near the diagonal [9], [20]. Thus, most elements of each row of the matrix Q (or QT) will occur near the matrix diagonal. Then applying each step i of the GE method to the matrix QT will induce non-zero elements in several adjacent rows to rowi.

In addition, during the second step of the GE method, the elements induced in row3 will produce more non-zero elements in the gap between the top elements of row3, row8 and row9, as well as the corresponding diagonal elements. This result is due to the aforementioned property: the elements of the QT matrices resulting from the PN models exist near the diagonal. The following algorithm illustrates how the set NE supports the calculation of the Kmin parameter.

Fig. 3. Reduction of VS 2  using MSRGR technique.
Fig. 3. Reduction of VS 2 using MSRGR technique.


Management of history analysis

Let the non-zero part of the row be that part of the row in which some of its elements are non-zero. To illustrate how the HA of the zero line portion and the non-zero line portion can be controlled, assume that the line is located in the upper diagonal region of VSm (ie, 0d i < Colbm). The HA of a non-zero rowim can be illustrated by applying all arithmetic operations registered in the history list corresponding to rowim to rowim; 0 d j d m-1.

On the other hand, no arithmetic operations will be registered in the history list corresponding to set A. On the contrary, we expect the history list to include records of arithmetic operations corresponding to the non-zero row parts of set B { {rowij ; li d j < di} where rowidi is the non-zero part of the row located in the diagonal region VSdi (ie Colbdi d i d Coledi). Given a set S, we can define the historical domain rowim (denoted by Domi) as follows.

Thus, the domain of the history of the parts of the zero row that extend higher than the highest part of the row of VSm is equal to I. To perform these processes, we use the same processes that were applied to the non-zero row. However, the state of rowim will only be changed if the computation operations are stored in PHLij; li d j d di are performed using non-zero row parts.

This limitation can be achieved by redefining the zero-rowim history domain as follows. Consequently, the Colej t um condition guarantees that the set richm; Colbj d k d Colej contains the row parts that are not zero. Our experience with the matrix Q generated from the PN system models shows that most of the non-zero elements of a vertical segment are concentrated in the diagonal region rows.

Numerical Results

Domim} where PHLij is part of the history list containing the computation operations performed during RA rowij. To illustrate the benefits of using the DBS technique, we applied DBS to the SRN model of the production Kanban system shown in the figure. In this figure, the presence of matrix elements near the diagonal can be observed.

The behavior of the DBS technique is the same as that of the GE technique when K = 0. Another part occurs during the retrieval and storage of the vertical segment elements (denoted ACCRS). From this figure, we can notice the difference between the number of history list records and that of the history list records accessed for the vertical segments of K=40.

Therefore, we can conclude that ACCHA greatly affects the performance of the DBS technique (i.e., the time to solution). For each vertical segment {VSi; 1d id K}, ACCHA is controlled by the history domain area of ​​the vertical segment VS (denoted by DomRi). The number of times the HD is accessed during the execution of the HA for the VS10 and the VS30 on the set PHLi; 1d in d40 when K=40 is shown in fig.

11 shows the change of the left and right sides of the history domain for parts of rows VS10 and those of VS30 for K =40 (i.e. The effect of the matrix diagonal on these sides of the history domain can be seen by the descending zigzag appearance of the diagrams shown in Fig. 17 increases exponentially due to of HA usage on the three aforementioned regions of VS10 and those in VS30.

Consequently, applying HA to boundary line segments will induce multiple elements for these line segments. The effect of RA can be shown in the sharp trend in the number of elements for the row parts of the diagonal region.

Fig. 5. The model of the kanban manufacturing system.
Fig. 5. The model of the kanban manufacturing system.


Computation of Accumulated Expected Reward Sensitivity of Rigid Markov Models." Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, Monte Carlo Resort, Las Vegas, Nevada, USA. Performance Analysis of the CORBA Event Service using Stochastic Reward nets.” Proceedings of the 19th Symposium on Dependable Distributed Systems, Nurnberg, Germany. Stochastic Fluid Petri Nets Augmented with Flush-out Arcs: Modeling and Analysis." Discrete Dynamic Event Systems: Theory & Applications, 11, No.

Steady-state analysis of infinite stochastic petri nets: Comparison of the spectral expansion and the matrix-geometric method." Proceedings of the 7th International Workshop on Petri Nets and Performance Models, Saint Malo, France. Algorithms for generating state-level representations of stochastic activity networks with general reward structures." IEEE Transactions on Software Engineering, 22, No. Quantifying the Dynamic Behavior of Process Algebras.” Proceedings of the Joint PAPM-PROBMIV Workshop, Aachen, Germany: Springer-Verlag, LNCS.

Compact representations of probability distributions in the analysis of superimposed Gspns.” Proceedings of the 9th International Workshop on Petri Nets and Performance Models, Aachen, Germany: IEEE CS Press. Numerical solution of Markov chains.” Proceedings of the 3rd International Conference on the Numerical Solution of Markov Chains. DSPNexpress: a software package for the efficient solution of deterministic and stochastic petri nets.” Performance evaluation, 22, no.

ﻤﺘﻌﻣ ﺪﻳﺪﺟ ﻚﻴﻨﻜﺗاﺪ

ﻠﻜﺸﻣ ﻞﺤﻟ ﺐﻠﺼﻟا صﺮﻘﻟا ﻲﻠﻋ تﺎﺒﺳﺎﺤﻟا تﻻﺎﺣ ﺮﺒﻛ ﺔ

ﺔﻳﺪﻴﻠﻘﺘﻟا ﺔﻴﺋاﻮﺸﻌﻟا يﺮﺘﺑ تﺎﻜﺒﺷ ﻪﺟﺬﻤﻧ قﺮﻃ ﻦﻋ ﺔﺠﺗﺎﻨﻟا ﺔﻴﻌﻗاﻮﻟا ﺔﻴﻠﻤﻌﻟا

ﻢﻳﺮﻛ دﻮﻤﺤﻣ ﺮﻴﻤـﺳ

ﻲﻨﻴﻠﻴﻜﻟا .س .و و

ﺚﺤﺒﻟا ﺺﺨﻠﻣ ،ﺔﻴﺋاﻮﺸﻌﻟا يﱰﺑ ﻪﻜﺒﺷ ﻞﺜﻣ ﺔﻴﺋاﻮﺸﻌﻟا ﻪﺟﺬﻤﻨﻟا ﻎﻴﺻ

و ﺔﻴﺋاﻮﺸﻌﻟا ﺔﻣﺎﻌﻟا يﱰﺑ ﻪﻜﺒﺷ

ﻦﻜﳝ ﺔﻴﺋاﻮﺸﻌﻟا ةﺄﻓﺎﻜﳌا يﱰﺑ ﻪﻜﺒﺷوأ

ﻞﻤﻌﻟ مﺪﺨﺘﺴﺗ ن تﺎﺒﺳﺎﺤﻠﻟ ﻲﻜﻴﻣﺎﻨﻳﺪﻟا كﻮﻠﺴﻠﻟ ﻢﻴﻘﺗو ﻪﺟﺬﳕ

ﺎﻴﺿﺎﻳر ﻢﺘﻳ ﺎﻬﻠﳊ ﻪﻧﺄﻓ ،ﻲﺋاﻮﺸﻌﻟا جذﻮﻤﻨﻟا اﺬﻫ ﻦﻣ فﻮﻛرﺎﻣ تﻻﺎﺣ جﺎﺘﻨﺘﺳا ﰎ ﱵﻣ .ﺔﻴﻌﻗاﻮﻟا ﺔﻴﻠﻤﻌﻟا ﻞﺼﺗ ﺔﺒﻴﻫر ةدﺎﻳز دادﺰﻳ ﺔﻓﻮﻔﺼﳌا ﻩﺬﻫ ﺮﺻﺎﻨﻋ دﺪﻋ .ﺔﻓﻮﻔﺼﻣ ةرﻮﺻ ﰲ ﺎﻬﻌﺿو

ﱃﻒﻟﻵا تﺎﺌﻣ


ﻧ ﺚﺤﺒﻟا اﺬﻫ ﰲ ﺎﻨﻧﺄﻓ ﺔﻠﻜﺸﳌا ﻩﺬﻫ ﻞﺜﻣ ﺎﻣﺪﺨﺘﺴﻣ تﺎﻓﻮﻔﺼﳌا مﺎﺴﻘﻧا" ﺔﻴﻠﻋ ﻖﻠﻄﻧ ﺪﻳﺪﺟ ﻚﻴﻨﻜﺗ مﺪﻘ

تﺎﻓﻮﻔﺼﳌا ﻢﻴﺴﻘﺗ ﰎ حﱰﻘﳌا ﻚﻴﻨﻜﺘﻟا اﺬﻫ ﰲ ."ﺐﻠﺼﻟا صﺮﻘﻟا تﺎﻴﻧﺎﻜﻣإﱃإ

مﺎﺴﻗﻷا ﻦﻣ دﺪﻋ

ﻠﻋ ﺎﻬﻨﻳﺰﲣو تﺎﻓﻮﻔﺼﳌاﻰ

ﺔﻴﻟﺎﻋ ةءﺎﻔﻜﺑ ﺐﻠﺼﻟا صﺮﻘﻟايﺪﻣ ﺢﻴﺿﻮﺘﻟو

ﰎ ﺪﻘﻠﻓ حﱰﻘﳌا ﻚﻴﻨﻜﺘﻟا ةءﺎﻔﻛ

ﻠﻋ ﻪﻘﻴﺒﻄﺗﻰ

ﻜﺒﺸﺑ ﻪﻤﻴﻤﺼﺗ ﰎ جذﻮﳕﺔ

ىﺪﺣﻹ ﻲﻜﻴﻣﺎﻨﻳﺪﻟا كﻮﻠﺴﻟا ﻞﺜﳝ ﻲﻜﻟ ﺔﻴﺋاﻮﺸﻌﻟا ةﺄﻓﺎﻜﳌا يﱰﺑ

ﻴﻌﻗاﻮﻟا ﺔﻴﻠﻤﻌﻟا تﺎﺒﺳﺎﳊا .فﻮﻛرﺎﻣ تﻻﺎﺣ ﻦﻣ ﻒﻟﻵا تﺎﺌﲟ ﺎﻧﺪﲤ ﱵﻟا ﺔ

Hình ảnh

Fig. 3. Reduction of VS 2  using MSRGR technique.
Fig. 5. The model of the kanban manufacturing system.
Fig. 6. The 18400x18400 Q T  of the kanban model.
Fig. 8. % increase in memory reduction, % increase in time for k  of  the DBS varying  from 20 to 200

Tài liệu tham khảo

Tài liệu liên quan

He is creator of the Tripod Project for School Improvement, faculty co-chair and director of the Achievement Gap Initiative at Harvard University, and was formerly the faculty