instruct8.5x11x2

8/4/2019 instruct8.5x11x2

1/4

221102

221102

22

221101

221101

11

0

P

PQ

QQ

PbPbbQ

aPaa

QQ

d

sd

s

d

sd

++= ++=

++=

++=

0= sidii QQE

) ( ) ( )

) ( ) ( ) 0

022211100

=++

=++

PP

PbaPbaba

Market Equilibrium: Parallelization of an algorithm

Patrcia Freitas BragaDoutorado em Modelagem Computacional e

Tecnologia IndustrialSENAI CIMATEC

Salvador, Brazile-mail: [email protected]

Marcus Fernandes da SilvaDoutorado em Modelagem Computacional e Tecnologia

IndustrialSENAI CIMATEC

Salvador, Brazile-mail: [email protected]

Abstract This paper shows a proposed parallelization in an

algorithm which calculates the market equilibrium. Aiming the

comparison between the serialized and the distributed

processing, a experimental procedure was made intending to

obtain data to evaluate the performance of the parallelization

applied to the algorithm. In the obtained results, was possible

to observe the gain in performance in the distributed

processing in the increasing of calculation complexity.

Keywords: market equilibrium, computational

parallelization, distributed processin.

I. CLOSEDMARKETMODELOF TWOGOODS

Let us first discuss a simple model in which only twogoods are related to each other. For simplicity, let us assumethat the functions of demand and supply of both goods arelinear. In parametric terms, this model can be written as

.

The coefficients a and b belong to the demand andsupply functions of goods and the coefficients andare attributed to the demand and supply functions of thesecond.As the first step in the solution of this model, we can use the

variable elimination. Replacing the second and thirdequations in the first one (for the first commodity) and thefifth and sixth equations in the fourth (for the secondcommodity), the model is reduced to two equations in twovariables:

Thesetwo

equations represent the equilibrium version condition ofexceed demand function (Ei) defined by:

(i=1,2,...,n)

for two goods, after replacing the demand and supply

functions in the two equilibrium conditions.Although this is a simple system of only two equations, thereare 12 parameters involved, and will be impractical usingalgebraic manipulations, unless using some kind ofshorthand notation. Therefore, we define the abbreviatedsymbols:

(i=0,1,2, )

Then, after moving theterms 0c and 0 to the

right side we get:

which can be solved by more variables eliminations. In thefirst equation we can find:

Replacing this expression in the second equation andsolving, we get:

Observes that it is expressed entirely in the data modelterms (parameters) as should be expressed as a value of thesolution. Using a similar process, we find the equilibriumprice of the second commodity:

2211

2211

+

+

PP

PcPc

iii

iii bac

(2

1102 c

PccP

+=

1221

2002

1

cc

ccP

=

1221

0110

2

cc

ccP

=


2/4

However, for these two values making sense, certainrestrictions must be imposed to the model. First, since thedivision by zero is undefined, we must demand that thecommon denominator of (6) and (7) are non-zero (nonzero),that is. Second, to ensure positive, the numerator must alsohave the same sign as the denominator.

Founded the equilibrium prices, balance quantities 1Q

and 2Q can be readily calculated by substituting (6) and(7) in the second (or third) equation and the fifth (or sixth)equation (1). These solution values are also naturallyexpressed in parameters terms. Before finding the system (5)solutions (6) and (7) it is essential considering the number ofsystem solutions. Before we make such considerations wefirst rewrite (5) in the following format:

Where we define

the coefficients square matrix of thislinear system

the constant elements row vector

the variables row vector of this system

By observing the system structure, it is necessary toimpose boundary conditions from the economy standpoint,

ie, it is essential that the system solutions become adapted toclosed market model. Deeming to this point, consider firstthat this system must be compatible, and certain non-trivial(show reference). For this to happen, we must necessarilyhave the A determinant as nonzero and the vectorelements should be totally or partially not null.

When we found the solutions (6) and (7), we are notconcerned to the observation of existence of a condition inthis system from the most important analys: the determinantof square matrix. And to calculate it is necessary to know itsdefinition. And so, we define the determinant of this matrixas ( ) [ ]AA det

Where ),...,,( 21 njjjJJ = is the number of

permutation inversions ( )njjj ,...,, 21 and indicatesthat the sum is over all permutations ( )n,...,2,1 . There area total of n! permutations (show reference).

II. PROBLEMTOSOLVE

We intend to develop a theoretical problem using the previous methodology applied to a market with a certainamount of goods, using the sequential and parallel programming. With this finality, we initially designed asequential algorithm which would start with the functionsdefinitions of supply and demand for these goods. Eachcoefficient of these functions would be determined by a drawof random numbers. Following the sequence, we would haveto solve a linear system like (5), but with the caveat that wehave a system with equations number and unknowns in theorder of certain products.

To find all the system equilibrium price will be used theGauss triangulation method (Barroso et al, 1987; BURIANet al, 2007; RUGGIERO and LOPES, 2009), which hasbeing a very efficient method, and one of the fastest to thesolution of linear systems (BURIAN et al, 2007, p.46).

The Gauss method has a small setback: in each iteration ofthe sequential method, it is essential that the diagonalelements of the coefficients matrix are nonzero, ie, in the

first interaction is necessary that the element is not zero, thesecond element is different from zero to the n interactionthe element is also different from zero. If all theseconditions are not met, the system will have no solution(RUGGIERO and LOPES, 2009, p. 127).

As we are in a limited computing environment, wepropose to stop the system resolution and restart it by doinga lot of new coefficients of the supply and demand functionsfor each commodity. It is computationally infeasible todetermine the initial number of solutions of this system bycalculating the determinant of the coefficients matrix, asobserved (5) because we would have added as many as thenumber of elements, which would be incompatible for alimited computing environment .

III. PARALLELIZATION PROPOSAL

Initially, we developed an algorithm to build themathematical structure of the market equilibrium, where wasused the Gauss method for solving the linear system, tocalculate the equilibrium price for a certain amount of products. We observed in the triangulation of the linearsystem there is a higher load processing in the algorithm,since for each array element, a new coefficient is calculatedbased on the pivot elements, until the system is triangular.As a result, the proposed parallelization focused on thistriangulation function, paralleling the calculations of thedeterminants.

We made some tests with the algorithm, and we foundthat, in the parallel processing with a larger number of processors, there was a gain in performance on thealgorithm, which its gaining was computed by using some parallel computing metrics, as showed in the followingsection IV.

IV. METRICSFORPARALLEL COMPUTING

We start this section by defining performance metrics for parallel computing which are used to evaluate the parallel

21

21

cc

2

1

P

P

c

21

21

ccA

0

0

cb

2

1

P

PX

[ ] ( )nnjjj

J aaaA ...121 21


3/4

application performance, based on the comparison ofexecution with multiple processors and running with oneprocessor.

Knowing the concept of performance metrics in parallelcomputing, it is possible to show that the purpose ofdeveloping sequential and parallel algorithms to theaforementioned problem is to measure the processing time of

these architectures making appropriate performancemeasurements in parallel computing. This aims to find thecomputer model (with the highest possible optimizationdegree) of a market equilibrium with n goods, to be useful inorder to contribute to future works, more detailed and relatedto this topic. We focused this work on the performancemeasurements of time processing: Speed-up and Efficiency.

A widely accepted definition for the first magnitude is ameasure of the observed speed increasing when performing agiven process p processors in relation to the implementationof this process in a processor (or the sequential algorithm)(MILANI, 2008). Then we have:

Where the time T1 is the time spent by the best existingsequential algorithm, or the time spent by a single processorto run the parallel algorithm that is being analyzed inparticular, ie, a single processor simulates the operation of pprocessors in parallel. And time Tp is the processing time ofthe parallelized algorithm which runs on p processors.The second quantity considered is a measure used inconjunction with the speedup. Shows the time fraction thatthe processors are being used. The efficiency calculation isgiven by the following equation (MILANI, 2008)

The ideal speedup and efficiency are, respectively, p 1,which is equivalent to say that the p processors availabilityincreases the speed of p times and that all processors arefully realized over time. However, for this occurs, theparallel algorithm would have to be such as no processor atany time should not do unnecessary work or stand stillwaiting for work. For several reasons, this scenario is notpossible in practice and a more realistic goal is to keep thevalue of efficiency as far as possible to zero as p increases(MILANI, 2008).

V. OBTAINED RESULTS

In the realized tests, were defined as commoditiesquantity 1 to 5 products, processed serially and in parallel (8processors), and finally were obtained the following results(Table I):

TABLE I. TABLEOF OBTAINED RESULTS

Qtd.products

Processors Time(miliseg)

Speed Up Efficiency

2 8

1

0.019073

4.081011

213,967965 26,7459956

3 8

1

0.016928

3.16000

186,672967 23,33412087

4 8

1

0.016928

5.375147

317,529950 39,69124375

5 8

1

0.021935

3.533125

161,072486 20,13406075

Since the coefficients of the linear system equations arerandom, there was difficulty in obtaining a number that werecompatible to the system calculations, and sometimes therewas not possible to obtain the matrix triangulation solution,therefore, was not possible to use larger values in tests .

Based on the results (Table I), we could observe the gaining

in overall performance, on the distributed parallel processing, since the computational execution weight wasdistributed on the algorithm.

VI. CONCLUSIONSAND FUTUREPERSPECTIVES

The parallelization has proven to be efficient whenusing the computational processes distribution in morecomplex execution. Using existing metrics, such as thespeed-up, you can get an idea of when is needed a greatercomputational power in certain algorithms. In this work, wasrealized that the increasing in the calculations complexityperformed by the algorithm, the greater was the demand forprocessing machines.

A critical point to this research relies on the randomnessof the coefficients to the equilibrium equations, which arethe coefficients of the linear system to be solved bytriangulation, which were not flexible enough and made thistask difficult, including to obtain higher values of products be tested. However, with the products amount drawn fortesting, was observed that the parallelization is justified incases of complex calculations, since the values of speed-upand calculation efficiency represents the performancegaining in the parallelization. Is expected the improvementof the algorithm to get higher values for extensive testing of

the algorithm efficiency.

REFERENCES

[1] L. Barroso. et al. Calculo Numrico com Aplicaes. 2 EdioSoPaulo. Editora Harba Ltda, 1987. 367p.

[2] R. Burian et al. Clculo Numrico. Editora LTC (Livros Tcnicos eCientficos Editora S.A.), 2007, 155p.

[3] A.. Chiang e K. Wainwrigth. Matemtica para Economistas.Traduo da4 Edio. So Paulo. Editora Elsevier, 2005, 659p.

pT

Tspeedup 1=

p

S

Ep

p =


4/4

[4] C. Milani. Estudo sobre a aplicao da computao paralela naresoluo de sistemas lineares . 76 f. Trabalho Final de Curso (Ps-Graduao em cincia da computao)- Pontifcia UniversidadeCtlica do Rio Grande do Sul, Porto Alegre, 2008..

[5] M. Ruggiero e V. Lopes. Clculo Numrico: Aspectos Tericos eComputacionais. 2 Edio. So Paulo. Editora Makron Books, 2009.406p.

[6] TAXAS DE CMBIO. In: BANCO CENTRAL DO BRASIL,2009.Disponvel em: . Acesso em: 17 de set. 2009.

Documents

instruct8.5x11x2