Partitioning sparse rectangular matrices for parallel computing of AATx
Seyrek dikdörtgensel matrislerin AATx (A A üssü T x)'in paralel işlemcilerde hesaplanabilmesi için parçalanması
- Tez No: 83743
- Danışmanlar: DOÇ. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Seyrek dikdörtgensel matrisler, hesap hiperçizgesi, haber leşme hiperçizgesi, hiperçizge parçalama, Sparse Rectangular Matrices, Computational Hypergraph Model, Communication Hypergraph Model, Hypergraph Partitioning
- Yıl: 1999
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Yazılımı Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 85
Özet
IV ÖZET SEYREK DİKDÖRTGENSEL MATRİSLERİN AATx'W PARALEL İŞLEMCİLERDE HESAPLANABİLMESİ İÇİN PARÇALANMASI Bora Uçar Bilgisayar ve Enformatik Mühendisliği, Yüksek Lisans Tez Yöneticisi: Doc. Dr. Cevdet Aykanat Eylül, 1999 Birçok bilimsel uygulama, bir seyrek dikdörtgensel matrisin bir vektör ve de aynı matrisin transpozunun bir başka vektör ile çarpılmasını içermektedir. Şimdiye kadar kullanılan çizge ve hiperçizge parçalanması algoritmalarında toplam haberleşme hacmi azaltılırken işlemciler arasındaki işlemsel denge, ma trisin tek boyutlu ayrıştırılması ile yakalanmaya çalışılmıştır. Bu tezde, toplam haberleşme sayısı ve hacmi iki yaklaşımla azaltılmaya çalışılmıştır. Genel haberleşme yaklaşımındaki birleşik haberleşme hacminin azaltılması problemi, matrislerin tek sınırlı çarpraz bloklar haline getirilmesi problemine dönüştü rülmüştür. Bu yaklaşımdaki birleşik ve toplam haberleşme sayısı paralel iş lemcilerin bağlantısına bağlı olup değiştirilememektedir. Kişiselleştirilmiş ha berleşme yaklaşımındaki toplam haberleşme sayısı ve hacmi iki aşamada azal tılmıştır. Birinci aşamada, toplam haberleşme hacmi azaltılırken işlemsel denge sağlanılmıştır. ikinci aşamada, önerilen haberleşme hiperçizgesi yardımı ile toplam haberleşme sayısı azaltılırken işlemciler arasında haberleşme işi dengesi sağlanmaya çalışılmıştır. Sunulan yöntemler birçok matris üzerinde sınanmış ve iyi yönde sonuçlar elde edilmiştir.
Özet (Çeviri)
Ill ABSTRACT PARTITIONING SPARSE RECTANGULAR MATRICES FOR PARALLEL COMPUTING OF AATx Bora Uçar M.S. in Computer Engineering and Information Science Supervisor: Asoc. Prof. Dr. Cevdet Aykanat Spetember, 1999 Many scientific applications involve repeated sparse matrix- vector and matrix- transpose- vector product computations. Graph and hypergraph partitioning based approaches used in the literature aim at minimizing the total commu nication volume while maintaining computational load balance through one dimensional partitioning of sparse matrices. In this thesis, we consider two approaches which consider minimizing both the total message count and com munication volume while maintaining balance on the communication loads of the processors. Two communication schemes are investigated for the fold and expand operations needed in the parallel algorithm. For the global communica tion scheme, we show that the problem of minimizing concurrent communica tion volume can be formulated as the problem of permuting the sparse matrix into a singly-bordered block-diagonal form, where the total and concurrent message count is determined by the interconnection topology. For the person alized communication scheme, a two stage approach is proposed. In the first stage, the total communication volume is minimized while maintaining balance on the computational loads of the processors. In the second stage, a novel com munication hypergraph model is proposed which enables the minimization of the total message count while maintaining balance on the communication loads of the processors through hypergraph-partitioning-like methods. The solution methods are tested on various matrices and results, which are quite attractive in terms of solution quality and running times, are obtained.
Benzer Tezler
- A parallel monolithic approach for the numerical simulation of fluid-structure interaction problems
Akışkan-yapı etkileşimi problemlerinin sayısal simülasyonu için paralel monolitik bir yöntem
ALİ EKEN
Doktora
İngilizce
2016
Havacılık Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. HAYRİ ACAR
DOÇ. DR. MEHMET ŞAHİN
- Distributed bipartite graph clustering
İki parçalı çizge demetleme
RESUL TUGAY
Yüksek Lisans
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ŞULE GÜNDÜZ ÖĞÜDÜCÜ
- Makine öğrenmesi kullanarak seyrek doğrusal sistemler için bölüm sayısını tahmin etme
Predicting sparse linear systems partition number using machinelearning
MOHAMED ABDIAZIZ HASSAN
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAnkara Yıldırım Beyazıt ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ FAHREDDİN ŞÜKRÜ TORUN
- Parallel sparse matrix-vector multiplies and iterative solvers
Paralel seyrek matris-vektör çarpımı ve dolaylı yöntemler
BORA UÇAR
Doktora
İngilizce
2005
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Latency-centric models and methods for scaling sparse operations
Seyrek işlemlerin ölçeklenebilmesi için gecikim-merkezli model ve yöntemler
REHA OĞUZ SELVİTOPİ
Doktora
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT