Resolução de Agrupamento Utilizando Suavização Hiperbólica com Arquitetura OpenMP
Autores
|
5522 |
Marcelo Lins de Souza
|
2531,47
|
|
5523 |
2531,47
|
Informações:
Publicações do PESC
A formulação matemática para solução do problema de agrupamento está associada a um modelo de mínima soma de quadrados. Este modelo produz um problema do tipo min-max-min, que além da sua natureza intrínsecamente multinível, tem a significativa característica de ser não diferenciável e de difícil solução (NP-Hard).
Com a finalidade de contornar estas dificuldades, utilizou-se a técnica de suavização hiperbólica, onde a solução final é obtida através da transformação do problema original em uma sequência de subproblemas diferenciáveis que gradualmente aproximam-se do problema original.
Neste trabalho propôs-se uma nova implementação para o método baseada na arquitetura OpenMP para paralelizar trechos do código, aproveitando os recursos de múltiplos processadores que os computadores atuais disponibilizam.
Para a comparação dos resultdos do XCM com o XCM-OpenMP, propôs-se uma "Arquitetura Orientada a Objetos para Comparação de Algoritmos".
Para confirmar experimentalmente o método proposto, resultados do XCM original (sequencial) e do XCM-OpenMP foram comparados. O melhor speed-up conseguido foi de 28 vezes. Os resultados obtidos com XCM-OpenMP não apresentam perda de precisão numérica.
The mathematical formulation for solving the clustering problem is associated with a minimum sum of squares model, producing a problem of type min-max-min.
This problem has intrinsic multi-level nature and has the significant characteristic of being non-diferentiable and NP-Hard.
In order to overcome these dificulties, the hyperbolic smoothing technique is used; the final solution is obtained by transforming the original problem into a sequence of differentiable subproblems which gradually approach the original problem.
In this work we proposed a new implementation of XCM based on the OpenMP architecture to parallelize parts of the code, using the resources of multiple processors that provide current computers. To compare the results between XCM and XCMOpenMP, an "Object-Oriented architecture to compare algorithms" was proposed.
To confirm experimentally the proposed method, the results of the original XCM (sequential) and the XCM-OpenMP are compared. The best achieved speed-up was 28. The numerical results obtained with XCM-OpenMP not exhibit loss of accuracy.