10 results on '"Uçar, Bora"'
Search Results
2. On Partitioning Problems with Complex Objectives
- Author
-
Kaya, Kamer, Rouet, François-Henry, Uçar, Bora, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Alexander, Michael, editor, D’Ambra, Pasqua, editor, Belloum, Adam, editor, Bosilca, George, editor, Cannataro, Mario, editor, Danelutto, Marco, editor, Di Martino, Beniamino, editor, Gerndt, Michael, editor, Jeannot, Emmanuel, editor, Namyst, Raymond, editor, Roman, Jean, editor, Scott, Stephen L., editor, Traff, Jesper Larsson, editor, Vallée, Geoffroy, editor, and Weidendorfer, Josef, editor
- Published
- 2012
- Full Text
- View/download PDF
3. Hypergraph Partitioning
- Author
-
Çatalyürek, Ümit V., Uçar, Bora, Aykanat, Cevdet, and Padua, David, editor
- Published
- 2011
- Full Text
- View/download PDF
4. Fill-in reduction in sparse matrix factorizations using hypergraphs
- Author
-
Kaya, Oguz, Kayaaslan, Enver, Uçar, Bora, Duff, Iain S., College of Computing (GATECH), Georgia Institute of Technology [Atlanta], Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique (CERFACS), STFC Rutherford Appleton Laboratory (RAL), Science and Technology Facilities Council (STFC), This work was partially supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program 'Investissements d’Avenir' (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR), and also by ANR project SOLHAR (ANR-13-MONU-0007). The research of I. S. Duff was supported in part by the EPSRC Grant EP/I013067/1., INRIA, ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), ANR-11-IDEX-0007,Avenir L.S.E.,PROJET AVENIR LYON SAINT-ETIENNE(2011), ANR-13-MONU-0007,SOLHAR,Solveurs pour architectures hétérogènes utilisant des supports d'exécution(2013), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), CERFACS, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
- Subjects
hypergraph partitioning ,sparse matrices ,LU factorization ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,QR factorization ,Fill-reducing orderings ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,direct methods ,Cholesky factorization - Abstract
We discuss the use of hypergraph partitioning based methods in fill-reducing orderings of sparse matrices for Cholesky, LU and QR factorizations. For the Cholesky factorization, we investigate a recent result on pattern-wise decomposition of sparse matrices, generalize the result, and develop algorithmic tools to obtain more effective ordering methods. The generalized results help us formulate the fill-reducing ordering problem for LU factorization as we do for the Cholesky case, without ever symmetrizing the given matrix $A$ as $|A| + |A^T|$ or $|^AT ||A|$. For the QR factorization, we adopt a recently proposed technique to use hypergraph models in a fairly standard manner. The method again does not form the possibly much denser matrix $|A^T ||A|$. We also discuss alternatives for LU and QR factorization cases where the symmetrized matrix can be used. We provide comparisons with the most common alternatives in all three cases.
- Published
- 2014
5. On analysis of partitioning models and metrics in parallel sparse matrix-vector multiplication
- Author
-
Catalyurek, Umit, Kaya, Kamer, Uçar, Bora, Department of Biomedical Informatics [Columbus], Ohio State University [Columbus] (OSU), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), INRIA, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
- Subjects
hypergraph partitioning ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Parallel sparse-matrix vector multiplication - Abstract
Graph/hypergraph partitioning models and methods have been successfully used to minimize the communication requirements among processors in several parallel computing applications. Parallel sparse matrix-vector multiplication~(SpMxV) is one of the representative applications that renders these models and methods indispensable in many scientific computing contexts. We investigate the interplay of several partitioning metrics and execution times of SpMxV implementations in three libraries: Trilinos, PETSc, and an in-house one. We design and carry out experiments with up to 512 processors and investigate the results with regression analysis. Our experiments show that the partitioning metrics, although not an exact measure of communication cost, influence the performance greatly in a distributed memory setting. The regression analyses demonstrate which metric is the most influential for the execution time of the three libraries used.
- Published
- 2013
6. Paralel seyrek matris-vektör çarpımı ve dolaylı yöntemler
- Author
-
Uçar, Bora, Aykanat, Cevdet, and Diğer
- Subjects
Iterative methods ,Hypergraph partitioning ,Sparse matrices ,Parallel matrix-vector multiplication ,QA188 .U23 2005 ,Preconditioning ,Approximate inverse preconditioner ,Sparse matrices Data processing ,Computer Engineering and Computer Science and Control ,Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol - Abstract
üOZETË üşPARALEL SEYREK MATRIS-VEKTOR CARPIMI VEüDOLAYLI YONTEMLERBora UşarcBilgisayar Mü hendisliği, Doktorau gTez Yüneticisi: Prof. Dr. Cevdet AykanatoAğustos, 2005gSeyrek matris-vektür carpımı (MxV) bir cok bilimsel hesaplama uygula-oş şmasının cekirdeğini oluşturmaktadır. Dolayısıyla, MxV carpımlarının par-ş g s şalelleştirilmesi, bilimsel hesaplama cevrelerinin ünem verdiği bir konudur. Bus ş o gkonuda yapılmış calışmalar yü k dengelemeye ve toplam haberleşme hacminisş s u sazaltmaya odaklanmıştır. Bu tezde, toplam haberleşme sayısının da ünemlis s oolabileceği güsterilmiştir.go s Ayrıca, işlemcilere düşen en bü yü k haberleşmes us uu shacminin ve sayısının niceliğinin de ünemli olabileceği güsterilmiştir. Bu dürtg o go s ohaberleşme ülşutü nü n azaltılmasını sağlayacak hiperşizge modelleri ve bu mod-s o cü u u g cellerin bülü mlenmesini sağlayacak yüntemler ünerilmiştir. Bu ünerilen model-ou g o o s olerin ve yüntemlerin, tek boyutlu ve iki boyutlu matris bülü mlendirilmesindeo ounasıl kullanılacağı güsterilmiştir. MxV işleminin en cok kullanıldıgı yer lineergo s s şsistem cüzü mlemelerinde kullanılan dolaylı yüntemlerdir. Bu dolaylı yüntemlerşo u o ocoğu zaman matris iyileştirme teknikleri kullanırlar. Matrislerin yaklaşık ters-şg s sleriyle iyileştirme tekniği, bir cok simetrik ve simetrik olmayan matris ceşitlerines g ş şsuygulanabilen ve cokşa kullanılan bir tekniktir. Bu teknik, temel olarak, MxVşcişleminin yerine ardışık MxV işlemlerini koyar. Yani, bir MxV işlemi, matrislerins s s syaklaşık tersleriyle iyileştirme tekniğini kullanan dolaylı yüntemlerde daha bü yü ks s g o uubir hesaplama işleminin sadece kü cuk bir parşasıdır. Ardışık MxV carpımlarınıns uşü c s şarasında etkileşim vardır. Bu etkileşimler, verimli paralelleştirme işin matris-s s s clerin bir arada bülü mlendirilmesini zorunlu kılmaktadır. Bu tezde, bir aradaoubülü mlendirmenin, değişik dolaylı yüntemler işin değişik matris bülü mlendirmeou gs o c gs oumodellerine yol aştıgı güsterilmiştir. Sıkşa kullanılan bir cok dolaylı yünteminc o s c ş ohangi matris bülü mlendirme modelleriyle paralelleştirilebileceği güsterilmiştir.ou s go sBu matris bülü mlendirme modellerinin elde edilmesini sağlamak işin, üncedenou g c oünerilmiş hiperşizge modellerini birleştirerek bileşik hiperşizge modelleri geliştireno s c s s c sviviiişlemler tanımlanmıştır. Bileşik hiperşizge modellerinin bülü mlenmesi ile ma-s s s c outrislerin bir arada bülü mlendirilebileceği güsterilmiştir. Yukarıda bahsedilenou go scalışmaların pratikte işe yarayıp yaramadıklarını gürmek işin, paralel MxVşs s o cişlemini yapan bir program yazdık. Bu programla yaptığımız deneyler sırasında,s gdaha genel bir paralel program sınıfının calışma sü resinin günder işlemlerininşs u o ssırasına bağlı olduğunu gürdü k. En iyi günder işlemi sırasının bazı varsayımlarg g ou o saltında nasıl bulunabileceğini güsterdik.g oAnahtar süzcükler : Seyrek matrisler, paralel matris-vektür carpımı, dolaylıou oşyüntemler, matris iyileştirme, matrislerin yaklaşık tersleriyle iyileştirme,o s s shiperşizge bülü mleme.c ou ABSTRACTPARALLEL SPARSE MATRIX-VECTOR MULTIPLIESAND ITERATIVE SOLVERSBora UşarcPh.D. in Computer EngineeringSupervisor: Prof. Dr. Cevdet AykanatAugust, 2005Sparse matrix-vector multiply (SpMxV) operations are in the kernel of manyscientiï¬c computing applications. Therefore, eï¬cient parallelization of SpMxVoperations is of prime importance to scientiï¬c computing community. Previousworks on parallelizing SpMxV operations consider maintaining the load balanceamong processors and minimizing the total message volume. We show that the to-tal message latency (start-up time) may be more important than the total messagevolume. We also stress that the maximum message volume and latency handledby a single processor are important communication cost metrics that should beminimized. We propose hypergraph models and hypergraph partitioning methodsto minimize these four communication cost metrics in one dimensional and twodimensional partitioning of sparse matrices. Iterative methods used for solvinglinear systems appear to be the most common context in which SpMxV operationsarise. Usually, these iterative methods apply a technique called preconditioning.Approximate inverse preconditioningâwhich can be applied to a large class ofunsymmetric and symmetric matricesâreplaces an SpMxV operation by a se-ries of SpMxV operations. That is, a single SpMxV operation is only a piece of alarger computation in the iterative methods that use approximate inverse precon-ditioning. In these methods, there are interactions in the form of dependenciesbetween the successive SpMxV operations. These interactions necessitate parti-tioning the matrices simultaneously in order to parallelize a full step of the subjectclass of iterative methods eï¬ciently. We show that the simultaneous partitioningrequirement gives rise to various matrix partitioning models depending on theiterative method used. We list the partitioning models for a number of widelyused iterative methods. We propose operations to build a composite hypergraphby combining the previously proposed hypergraph models and show that par-titioning the composite hypergraph models addresses the simultaneous matrixpartitioning problem. We strove to demonstrate how the proposed partitioningivvmethodsâboth the one that addresses multiple communication cost metrics andthe other that addresses the simultaneous partitioning problemâhelp in practice.We implemented a library and investigated the performances of the partitioningmethods. These practical investigations revealed a problem that we call messageordering problem. The problem asks how to organize the send operations to min-imize the completion time of a certain class of parallel programs. We show howto solve the message ordering problem optimally under reasonable assumptions.Keywords: Sparse matrices, parallel matrix-vector multiplication, iterative meth-ods, preconditioning, approximate inverse preconditioner, hypergraph partition-ing. 156
- Published
- 2005
7. Seyrek dikdörtgensel matrislerin AATx (A A üssü T x)'in paralel işlemcilerde hesaplanabilmesi için parçalanması
- Author
-
Uçar, Bora, Aykanat, Cevdet, and Diğer
- Subjects
Matrices ,Computational Hypergraph Model ,Partitions (Mathematics) ,Communication ,Communication Hypergraph Model ,Hypergraph ,Hypergraph Partitioning ,Hypergraphs ,Sparse Rectangular Matrices ,Computer Engineering and Computer Science and Control ,QA165 .U23 1999 ,Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol - Abstract
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. Anahtar kelimeler: Seyrek dikdörtgensel matrisler, hesap hiperçizgesi, haber leşme hiperçizgesi, hiperçizge parçalama. 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. Key words: Sparse Rectangular Matrices, Computational Hypergraph Model, Communication Hypergraph Model, Hypergraph Partitioning. 74
- Published
- 1999
8. A Matrix Partitioning Interface to PaToH in MATLAB
- Author
-
Uçar, Bora, Çatalyürek, Ümit V., and Aykanat, Cevdet
- Subjects
- *
COMPUTER interfaces , *HYPERGRAPHS , *SPARSE matrices , *PARALLEL algorithms , *PARTITIONS (Mathematics) , *RECURSIVE functions , *ORTHOGONALIZATION - Abstract
Abstract: We present the PaToH MATLAB Matrix Partitioning Interface. The interface provides support for hypergraph-based sparse matrix partitioning methods which are used for efficient parallelization of sparse matrix–vector multiplication operations. The interface also offers tools for visualizing and measuring the quality of a given matrix partition. We propose a novel, multilevel, 2D coarsening-based 2D matrix partitioning method and implement it using the interface. We have performed extensive comparison of the proposed method against our implementation of orthogonal recursive bisection and fine-grain methods on a large set of publicly available test matrices. The conclusion of the experiments is that the new method can compete with the fine-grain method while also suggesting new research directions. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
9. ENCAPSULATING MULTIPLE COMMUNICATION-COST METRICS IN PARTITIONING SPARSE RECTANGULAR MATRICES FOR PARALLEL MATRIX-VECTOR MULTIPLIES.
- Author
-
Uçar, Bora and Aykanat, Cevdet
- Subjects
- *
MATRICES (Mathematics) , *ALGEBRA , *ABSTRACT algebra , *MATHEMATICS , *VERSIFICATION - Abstract
This paper addresses the problem of one-dimensional partitioning of structurally unsymmetric square and rectangular sparse matrices for parallel matrix-vector and matrix-transpose-vector multiplies. The objective is to minimize the communication cost while maintaining the balance on computational loads of processors. Most of the existing partitioning models consider only the total message volume hoping that minimizing this communication-cost metric is likely to reduce other metrics. However, the total message latency (start-up time) may be more important than the total message volume. Furthermore, the maximum message volume and latency handled by a single processor are also important metrics. We propose a two-phase approach that encapsulates all these four communication-cost metrics. The objective in the first phase is to minimize the total message volume while maintaining the computational-load balance. The objective in the second phase is to encapsulate the remaining three communication-cost metrics. We propose communication-hypergraph and partitioning models for the second phase. We then present several methods for partitioning communication hypergraphs. Experiments on a wide range of test matrices show that the proposed approach yields very effective partitioning results. A parallel implementation on a PC cluster verifies that the theoretical improvements shown by partitioning results hold in practice. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
10. Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices
- Author
-
Aykanat, Cevdet, Cambazoglu, B. Barla, and Uçar, Bora
- Subjects
- *
HYPERGRAPHS , *ALGORITHMS , *GRAPH theory , *FUZZY hypergraphs - Abstract
Abstract: -way hypergraph partitioning has an ever-growing use in parallelization of scientific computing applications. We claim that hypergraph partitioning with multiple constraints and fixed vertices should be implemented using direct -way refinement, instead of the widely adopted recursive bisection paradigm. Our arguments are based on the fact that recursive-bisection-based partitioning algorithms perform considerably worse when used in the multiple constraint and fixed vertex formulations. We discuss possible reasons for this performance degradation. We describe a careful implementation of a multi-level direct -way hypergraph partitioning algorithm, which performs better than a well-known recursive-bisection-based partitioning algorithm in hypergraph partitioning with multiple constraints and fixed vertices. We also experimentally show that the proposed algorithm is effective in standard hypergraph partitioning. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.