instruct8.5x11x2

Embed Size (px)

Citation preview

  • 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

    =

  • 8/4/2019 instruct8.5x11x2

    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

  • 8/4/2019 instruct8.5x11x2

    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 =

  • 8/4/2019 instruct8.5x11x2

    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.