Εφαρμογή μεθόδων παράλληλης επεξεργασίας στη μελέτη της ταλαντωτικής συμπεριφοράς σύνθετων μηχανικών συστημάτων

Abstract

The use of Automated Multilevel Substructuring (AMLS), for the analysis of constantly bigger models created the need for the extension of the method to systems of parallel processing. The main characteristic of the method is that for an efficient implementation a number of choices have to be made regarding the algorithms used in the intermediate steps. In this dissertation a fully distributed version of the general AMLS methodology has been designed and implemented (called MLDS) and the factors which influence the efficiency of the algorithm have been analyzed. For this purpose, the solution of static problems and symmetric eigenproblems has been studied as well. Initially, the Cholesky factorization of dense matrices and the multifrontal method for the factorization of sparse matrices were presented. For the parallelization of the latter a static weighted subtree to subcube mapping has been used. As the number of processors increases the efficiency decreases due to the growth of the volume of communication and the load imbalance because of the static mapping. Afterwards, the Lanczos method was described and two methods of its parallelization were discussed. With the first method, the frequency interval of interest is divided in subintervals each of which is processed by one processor. Although, no communication between the processors is required, the efficiency is limited because of the different calculation cost if each subinterval. In addition, the distributed execution usually involves a greater number of numerical operations than the corresponding serial one. With the second method, the most time consuming operations of the solution of static problems and orthogonalization are individually parallelized. The efficiency is low because of the high cost of communication. Finally, the MLDS algorithm was presented. First the identification of the mathematical substructures and the creation of the assembly tree were discussed. Then the parallelization of the intermediate steps was described. Briefly, all the processors are divided in groups, except for one, which is called main global process. Each substructure is assigned to a group. The purpose of the main global process is to prepare, send and collect the data involved in the various staged of the processing of each substructure. Generally, the accuracy and efficiency of the algorithm depends on the number of levels of the assembly tree and the cut-off frequency of the individual eigenproblems.

Η εφαρμογή της μεθόδου της Αυτοματοποιημένης Σύνθεσης Υπολακατασκευών (AMLS), σε ολοένα και μεγαλύτερα μοντέλα κατέστησε επιτακτική την ανάγκη της επέκτασής της σε συτήματα παράλληλης επεξεργασίας. Το κύριο χαρακτηριστικό της μεθόδου είναι ότι για την αποδοτική υλοποίησή της είναι αναγκαία η προσεκτική επιλογή των αλγορίθμων που θα χρησιμοποιηθούν στα επιμέρους βήματά της. Στην παρούσα εργασία σχεδιάστηκε και υλοποίηθηκε μία πλήρως κατανεμημένη εκδοχή της μεθοδολογίας AMLS (που ονομάστηκε MLDS) και διερευνήθηκαν οι παράγοντες που επηρεάζουν την απόδοση της παραλληλοποίησης. Για το σκοπό αυτό μελετήθηκαν οι αλγόριθμοι επίλυσης στατικών προβλημάτων και ιδιοπροβλημάτων αραιών και πλήρων μητρώων. Αρχικά, αναλύθηκε η παραγοντοποίηση Cholesky για πλήρη μητρώα και η μέθοδος πολλαπλών μετώπων για την παραγοντοποίηση αραιών μητρώων. Για την παραλληλοποίηση της τελευταίας χρησιμοποιήθηκε στατική σταθμισμένη αντιστοίχιση υποδέντρου σε υποκύβο. Όσο αυξάνει ο αριθμός των επεξεργαστών η αποδοση της παραλληλοποίησης περιορίζεται λόγω της αύξησης του όγκου επικοινωνίας και της ανισοκατανομής του φορτιου λόγω της στατικής αντιστοίχισης. Στη συνέχεια, περιγράφηκε η μέθοδος του Lanczos και συζητήθηκαν δύο μέθοδοι παραλληλοποίησης. Η πρώτη αφορά στο χωρισμό του ζητούμενου εύροους συχνοτήτων σε διαστήματα και την ανεξάρτητη επεξεργασία κάθε διαστήματος από έναν επεξεργαστή. Με τη μέθοδο αυτή δεν απαιτείται επικοινωνία μεταξύ των επεξεργαστών, ωστόσο η απόδοση περιορίζεται εξαιτίας του διαφορετικού κόστους της επεξεργασίας κάθε υποδιαστήματος. Επίσης, συνήθως η κατανεμημένη εκτέλεση περιλαμβάνει μεγαλύτερο αριθμό αριθμητικών πράξεων από τη σειριακή. Η δέυτερη μέθοδος αφορά στην επιμέρους παραλληλοποίηση των χρονοβόρων πράξεων της επίλυσης στατικών προβλημάτων και της ορθογωνιοποίησης και είχε μικρή απόδοση λόγω υψηλού κόστους επικοινωνίας. Τέλος, παρουσιάστηκε ο αλγόριθμος MLDS. Αφού συζητήθηκε ο τρόπος χωρισμού σε μαθηματικές υποκατασκευές, περιγράφηκε η παραλληλοποίηση των επιμέρους βημάτων. Περιληπτικά, οι διαθέσιμοι επεξεργαστές πλην ενός που ονομάζεται κύρια καθολική διεργασία, χωρίζονται σε υποσύνολα στα οποία ανατίθενται οι υποκατασκευές. Η κύρια καθολική διεργασία αναλαμβάνει να προετοιμάσει, να αποστείλει και να συλλέξει τα κατάλληλα δεδομένα που συμμετέχουν στα διάφορα στάδια της επεξεργασίας κάθε υποκατασκευής. Γενικά, η ακρίβεια και η απόδοση του αλγορίθμου εξαρτάται από τον αριθμό των επιπέδων του δέντρου σύνθεσης και της συχνότητα επίλυσης των επιμέρους ιδιοπρβλημάτων.