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, Hiperçizgeler, Matrisler, İletişim, Sparse Rectangular Matrices, Computational Hypergraph Model, Communication Hypergraph Model, Hypergraph Partitioning, Hypergraphs, Matrices, Communication
- 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ı: Belirtilmemiş.
Ö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
- Hypergraph models for sparse matrix partitioning and reordering
Seyrek matris bölümleme ve yeniden-düzenleme için hiperçizge modelleri
ÜMİT VEYSEL ÇATALYÜREK
Doktora
İngilizce
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Yazılımı Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Sparse lineer denklem sistemlerinin paralel metodlarla çözüm yöntemleri
Solution of sparse linear systems on a cluster of workstations using graph partitianing methods
BETÜL TURHAL
Yüksek Lisans
Türkçe
2000
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı (disiplinlerarası)
PROF. DR. KAYHAN ERCİYES
- Graph and hypergraph partitioning
Çizge ve hiperçizge parçalama
ALİ DAŞDAN
Yüksek Lisans
İngilizce
1993
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CEVDET AYKANAT
- Parallel algorithms for the solution of large sparse linear inequality systems on distributed memory architectures
Dağıtık bellek mimarilerinde büyük seyrek lineer eşitsizlik sistemlerinin çözümü için paralel algoritmalar
TURNA ESMA
Yüksek Lisans
İngilizce
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. PINAR Ç. MUSTAFA
- A Constructive multi-way circuil partitioning algorithm based on minimum degree ordering
Minimum derece sıralamasına dayalı yapıcı çok kısımlı devre parçalama algoritması
ÜMİT V. ÇATALYÜREK
Yüksek Lisans
İngilizce
1994
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CEVDET AYKANAT