It is well recognized the convenience of converting the linearly constrained convex optimization problems to a monotone variational inequality.Recently,we have proposed a unified algorithmic framework which can guide ...It is well recognized the convenience of converting the linearly constrained convex optimization problems to a monotone variational inequality.Recently,we have proposed a unified algorithmic framework which can guide us to construct the solution methods for solving these monotone variational inequalities.In this work,we revisit two full Jacobian decomposition of the augmented Lagrangian methods for separable convex programming which we have studied a few years ago.In particular,exploiting this framework,we are able to give a very clear and elementary proof of the convergence of these solution methods.展开更多
Graph is a well known data structure to represent the associated relationships in a variety of applications,e.g.,data science and machine learning.Despite a wealth of existing efforts on developing graph processing sy...Graph is a well known data structure to represent the associated relationships in a variety of applications,e.g.,data science and machine learning.Despite a wealth of existing efforts on developing graph processing systems for improving the performance and/or energy efficiency on traditional architectures,dedicated hardware solutions,also referred to as graph processing accelerators,are essential and emerging to provide the benefits significantly beyond what those pure software solutions can offer.In this paper,we conduct a systematical survey regarding the design and implementation of graph processing accelerators.Specifically,we review the relevant techniques in three core components toward a graph processing accelerator:preprocessing,parallel graph computation,and runtime scheduling.We also examine the benchmarks and results in existing studies for evaluating a graph processing accelerator.Interestingly,we find that there is not an absolute winner for all three aspects in graph acceleration due to the diverse characteristics of graph processing and the complexity of hardware configurations.We finally present and discuss several challenges in details,and further explore the opportunities for the future research.展开更多
Graph coloring has a wide range of real world applications,such as in the operations research,communication network,computational biology and compiler optimization fields.In our recent work[1],we propose a divide-andc...Graph coloring has a wide range of real world applications,such as in the operations research,communication network,computational biology and compiler optimization fields.In our recent work[1],we propose a divide-andconquer approach for graph coloring,called VColor.Such an approach has three generic subroutines.(i)Graph partition subroutine:VColor partitions a graph G into a vertex cut partition(VP),which comprises a vertex cut component(VCC)and small non-overlapping connected components(CCs).(ii)Component coloring subroutine:VColor colors the VCC and the CCs by efficient algorithms.(iii)Color combination subroutine:VColor combines the local colors by exploiting the maximum matchings of color combination bigraphs(CCBs).VColor has revealed some major bottlenecks of efficiency in these subroutines.Therefore,in this paper,we propose VColor^(*),an approach which addresses these efficiency bottlenecks without using more colors both theoretically and experimentally.The technical novelties of this paper are the following.(i)We propose the augmented VP to index the crossing edges of the VCC and the CCs and propose an optimized CCB construction algorithm.(ii)For sparse CCs,we propose using a greedy coloring algorithm that is of polynomial time complexity in the worst case,while preserving the approximation ratio.(iii)We propose a distributed graph coloring algorithm.Our extensive experimental evaluation on real-world graphs confirms the efficiency of VColor^(*).In particular,VColor^(*)is 20X and 50X faster than VColor and uses the same number of colors with VColor on the Pokec and PA datasets,respectively.VColor^(*)also significantly outperforms the state-ofthe-art graph coloring methods.展开更多
基金The author was supported by the NSFC Grant No.11871029.
文摘It is well recognized the convenience of converting the linearly constrained convex optimization problems to a monotone variational inequality.Recently,we have proposed a unified algorithmic framework which can guide us to construct the solution methods for solving these monotone variational inequalities.In this work,we revisit two full Jacobian decomposition of the augmented Lagrangian methods for separable convex programming which we have studied a few years ago.In particular,exploiting this framework,we are able to give a very clear and elementary proof of the convergence of these solution methods.
基金the National Key Research and Development Program of China under Grant No.2018YFB1003502the National Natural Science Foundation of China under Grant Nos.61825202,61832006,61628204 and 61702201.
文摘Graph is a well known data structure to represent the associated relationships in a variety of applications,e.g.,data science and machine learning.Despite a wealth of existing efforts on developing graph processing systems for improving the performance and/or energy efficiency on traditional architectures,dedicated hardware solutions,also referred to as graph processing accelerators,are essential and emerging to provide the benefits significantly beyond what those pure software solutions can offer.In this paper,we conduct a systematical survey regarding the design and implementation of graph processing accelerators.Specifically,we review the relevant techniques in three core components toward a graph processing accelerator:preprocessing,parallel graph computation,and runtime scheduling.We also examine the benchmarks and results in existing studies for evaluating a graph processing accelerator.Interestingly,we find that there is not an absolute winner for all three aspects in graph acceleration due to the diverse characteristics of graph processing and the complexity of hardware configurations.We finally present and discuss several challenges in details,and further explore the opportunities for the future research.
基金the support of NSF of China(61773167,61929103)NSF of Shandong Province(ZR2019LZH006)+1 种基金NSF of Shanghai(17ZR1444900,HKRGC GRF 12201119,12232716 and 12201518)QLUT Young Scholar Program(2018DBSHZ005).
文摘Graph coloring has a wide range of real world applications,such as in the operations research,communication network,computational biology and compiler optimization fields.In our recent work[1],we propose a divide-andconquer approach for graph coloring,called VColor.Such an approach has three generic subroutines.(i)Graph partition subroutine:VColor partitions a graph G into a vertex cut partition(VP),which comprises a vertex cut component(VCC)and small non-overlapping connected components(CCs).(ii)Component coloring subroutine:VColor colors the VCC and the CCs by efficient algorithms.(iii)Color combination subroutine:VColor combines the local colors by exploiting the maximum matchings of color combination bigraphs(CCBs).VColor has revealed some major bottlenecks of efficiency in these subroutines.Therefore,in this paper,we propose VColor^(*),an approach which addresses these efficiency bottlenecks without using more colors both theoretically and experimentally.The technical novelties of this paper are the following.(i)We propose the augmented VP to index the crossing edges of the VCC and the CCs and propose an optimized CCB construction algorithm.(ii)For sparse CCs,we propose using a greedy coloring algorithm that is of polynomial time complexity in the worst case,while preserving the approximation ratio.(iii)We propose a distributed graph coloring algorithm.Our extensive experimental evaluation on real-world graphs confirms the efficiency of VColor^(*).In particular,VColor^(*)is 20X and 50X faster than VColor and uses the same number of colors with VColor on the Pokec and PA datasets,respectively.VColor^(*)also significantly outperforms the state-ofthe-art graph coloring methods.
