From b432a193ce522320f89b2e60741fa33c04fdfe68 Mon Sep 17 00:00:00 2001 From: Peter Munch Date: Sat, 23 Apr 2022 22:42:57 +0200 Subject: [PATCH] Draft --- 9.4/paper.bib | 89 +++ 9.4/paper.tex | 463 ++++++++++++++-- 9.4/svg/repartitioning.pdf_tex | 72 +++ 9.4/svg/repartitioning.svg | 976 +++++++++++++++++++++++++++++++++ 4 files changed, 1568 insertions(+), 32 deletions(-) create mode 100644 9.4/svg/repartitioning.pdf_tex create mode 100644 9.4/svg/repartitioning.svg diff --git a/9.4/paper.bib b/9.4/paper.bib index 724cc3b..809236a 100644 --- a/9.4/paper.bib +++ b/9.4/paper.bib @@ -66,6 +66,13 @@ Url = {https://www.dealii.org/developer/doxygen/deal.II/changes_between_9_2_0_and_9_3_0.html} } +@Misc{changes94, + key={List of Changes}, + Title = {List of Changes for 9.4}, + Note = {\url{https://www.dealii.org/developer/doxygen/deal.II/changes_between_9_3_0_and_9_4_0.html}}, + Url = {https://www.dealii.org/developer/doxygen/deal.II/changes_between_9_3_0_and_9_4_0.html} +} + @article{dealII80, title = {The \texttt{deal.II} Library, Version 8.0}, author = {W. Bangerth and T. Heister and L. Heltai and G. Kanschat @@ -182,6 +189,24 @@ doi = "10.1515/jnma-2018-0054" url = {https://doi.org/10.1515/jnma-2020-0043} } +@article{dealII93, + title = {The \texttt{deal.II} Library, Version 9.3}, + author = {Daniel Arndt and Wolfgang Bangerth and Bruno Blais and + Marc Fehling and Rene Gassm{\"o}ller and Timo Heister + and Luca Heltai and Uwe K{\"o}cher and Martin + Kronbichler and Matthias Maier and Peter Munch and + Jean-Paul Pelteret and Sebastian Proell and Konrad + Simon and Bruno Turcksin and David Wells and Jiaqi + Zhang}, + journal = {Journal of Numerical Mathematics}, + year = {2021}, + url = {https://dealii.org/deal93-preprint.pdf}, + doi = {10.1515/jnma-2021-0081}, + volume = {29}, + number = {3}, + pages = {171--186} +} + %% The deal.II web page and online reference. %% Please cite specific versions only if you really need to @@ -1218,3 +1243,67 @@ doi = {10.1504/IJCSE.2009.029164} archivePrefix={arXiv}, primaryClass={cond-mat.mtrl-sci} } + +@article{burstedde2020parallel, + title={Parallel tree algorithms for AMR and non-standard data access}, + author={Burstedde, Carsten}, + journal={ACM Transactions on Mathematical Software (TOMS)}, + volume={46}, + number={4}, + pages={1--31}, + year={2020}, + publisher={ACM New York, NY, USA} +} + +@article{mirzadeh2016parallel, + title={Parallel level-set methods on adaptive tree-based grids}, + author={Mirzadeh, Mohammad and Guittet, Arthur and Burstedde, Carsten and Gibou, Frederic}, + journal={Journal of Computational Physics}, + volume={322}, + pages={345--364}, + year={2016}, + publisher={Elsevier} +} + +@article{hoefler2010scalable, + title={Scalable communication protocols for dynamic sparse data exchange}, + author={Hoefler, Torsten and Siebert, Christian and Lumsdaine, Andrew}, + journal={ACM Sigplan Notices}, + volume={45}, + number={5}, + pages={159--168}, + year={2010}, + publisher={ACM New York, NY, USA} +} + +@article{ibanez2016pumi, + title={PUMI: Parallel unstructured mesh infrastructure}, + author={Ibanez, Daniel A and Seol, E Seegyoung and Smith, Cameron W and Shephard, Mark S}, + journal={ACM Transactions on Mathematical Software (TOMS)}, + volume={42}, + number={3}, + pages={1--28}, + year={2016}, + publisher={ACM New York, NY, USA} +} + +@article{munch2022gc, + title={Efficient distributed matrix-free multigrid methods on locally refined meshes for FEM computations}, + author= {Munch, Peter and Heister, Timo and Prieto Saavedra, Laura and Kronbichler, Martin}, + year= {2022}, + url = {https://arxiv.org/abs/2203.12292} +} + +@article{munch2022hn, + title = {Efficient application of hanging-node constraints for matrix-free high-order FEM computations on CPU and GPU}, + author = {Munch, Peter and Ljungkvist, Karl and Kronbichler, Martin}, + year = {2022, accepted for publication}, +} + +@inproceedings{ljungkvist2017matrix, + title={Matrix-free finite-element computations on graphics processors with adaptively refined unstructured meshes.}, + author={Ljungkvist, Karl}, + booktitle={SpringSim (HPC)}, + pages={1--1}, + year={2017} +} \ No newline at end of file diff --git a/9.4/paper.tex b/9.4/paper.tex index c8596ef..ad50bb4 100644 --- a/9.4/paper.tex +++ b/9.4/paper.tex @@ -22,6 +22,8 @@ %\renewcommand{\baselinestretch}{2.0} +\graphicspath{{svg/}} + \usepackage[normalem]{ulem} \usepackage{todonotes} @@ -92,7 +94,7 @@ cross/.default={2pt}} \affil[6]{School of Mathematical and Statistical Sciences, Clemson University, Clemson, SC, 29634, USA - {\texttt{heister/jiaqi2@clemson.edu}}} + {\texttt{heister@clemson.edu}}} \author[7]{Luca~Heltai} \affil[7]{SISSA, @@ -105,7 +107,7 @@ cross/.default={2pt}} \affil[9]{Institute for Computational Mechanics, Technical University of Munich, Boltzmannstr.~15, 85748 Garching, Germany. - {\texttt{kronbichler/munch/proell@lnm.mw.tum.de}}} + {\texttt{kronbichler/munch@lnm.mw.tum.de}}} \affil[10]{Department of Information Technology, Uppsala University, Box 337, 751\,05 Uppsala, Sweden. @@ -158,7 +160,7 @@ cross/.default={2pt}} \begin{abstract} This paper provides an overview of the new features of the finite element - library \dealii, version 9.3. + library \dealii, version 9.4. \end{abstract} @@ -180,11 +182,15 @@ GNU Lesser General Public License (LGPL). Downloads are available at The major changes of this release are: % \begin{itemize} - \item TODO; - \item TODO new tutorial programs and a new code gallery program (see Section~\ref{subsec:steps}). + \item Advances in simplex- and mixed-mesh support (see Section~\ref{sec:simplex}); + \item Repartitioning of distributed meshes (see Section~\ref{sec:repartitioning}); + \item Advances in matrix-free infrastructure (see Section~\ref{sec:mf}); + \item Advances in multigrid infrastructure (see Section~\ref{sec:multigrid}); + \item CutFEM support (see Section~\ref{sec:cut}); + \item Performance improvement of particle infrastructure (see Section~\ref{sec:particles}); + \item Two new tutorial programs and a new code gallery program (see Section~\ref{subsec:steps}). \end{itemize} % -In addition, we discuss the \candi{} installation program in Section~\ref{subsec:candi}. While all of these major changes are discussed in detail in Section~\ref{sec:major}, there @@ -192,10 +198,24 @@ are a number of other noteworthy changes in the current \dealii{} release that we briefly outline in the remainder of this section: % \begin{itemize} - \item TODO. +% \item \texttt{AffineConstraints::make\_consistent\_in\_parallel()} allows +% to make constraints consistent in parallel. + \item \texttt{DataOutResample} does not output a numerical solution + on the cells of the original triangulation but interpolates the result + onto a second triangulation (that can be completely unrelated). + By using this class, one can output the result obtained on an + unstructured mesh on a structured one, which might be a more + memory-efficient storage format, or one can create a slice in 3D. + \item The new function \texttt{find\_point\_owner\_rank()} of \texttt{parallel::distributed::Triangulation} allows to find the MPI + rank of the subdomain of a distributed mesh that contains a given point. + It is communication-free, leverages the functionality of p4est (>v.2.2), + and its algorithm is described in \cite{burstedde2020parallel}. Based on the obtained information, + communication pattern in \texttt{Utilties::MPI::RemotePointEvaluation} can be set up efficiently. Furthermore, this feature could be used in the future to allow + particle simulations, where particle movement is not + limited by CFL conditions, as done in \cite{mirzadeh2016parallel}. \end{itemize} % -The changelog lists more than 200 other features and bugfixes. +The changelog lists more than 150 other features and bugfixes. @@ -217,27 +237,347 @@ can be found %\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\subsection{Topic 1} +\subsection{Advances in simplex- and mixed-mesh support}\label{sec:simplex} + +We continued to work on the simplex- and mixed-mesh support. We fixed +many bugs and generalized existing functions that only worked for +hypercube shaped cells. Most notable new functions are: + +\begin{figure}[!t] + + \centering + + + \begin{tikzpicture}[scale=1.7] + + \coordinate (0) at (0,0); + \coordinate (1) at (1,0); + \coordinate (2) at (0,1); + + \coordinate (3) at (0,0.5); + \coordinate (4) at (0.5,0.5); + \coordinate (5) at (0.5,0); + + \foreach \i in {0,1, 2, 3, 4, 5} + \draw[blue,fill=blue] (\i) circle (1.1pt) node [below] {}; + + + \draw (0) --(1) -- (2) -- (0); + \draw (3) --(4) -- (5) -- (3); + + \end{tikzpicture} + \qquad\qquad + \begin{tikzpicture}[scale=1.3] + + \coordinate (0) at (0,0,0); + \coordinate (1) at (0,0,1); + \coordinate (2) at (1,0,0); + \coordinate (3) at (0,1,0); + \coordinate (4) at (0,0,0.5); + \coordinate (6) at (0.5,0,0); + \coordinate (7) at (0,0.5,0); + \coordinate (5) at (0.5,0.0,0.5); + \coordinate (8) at (0.0,0.5,0.5); + \coordinate (9) at (0.5,0.5,0.0); + + \draw (0) -- (1) -- (2) -- (0); + \draw (0) -- (1) -- (3) -- (0); + \draw (1) -- (2) -- (3) -- (1); + + \draw[-, fill=red!30, opacity=.5] (4)--(6)--(7)--cycle; + \draw[-, fill=red!30, opacity=.5] (0)--(6)--(7)--cycle; + \draw[-, fill=red!30, opacity=.5] (0)--(4)--(7)--cycle; + \draw[-, fill=red!30, opacity=.5] (0)--(4)--(6)--cycle; + + \draw[-, fill=blue!30, opacity=.5] (1)--(4)--(5)--cycle; + \draw[-, fill=blue!30, opacity=.5] (1)--(4)--(8)--cycle; + \draw[-, fill=blue!30, opacity=.5] (4)--(5)--(8)--cycle; + \draw[-, fill=blue!30, opacity=.5] (1)--(5)--(8)--cycle; + + \draw[-, fill=green!30, opacity=.5] (2)--(5)--(6)--cycle; + \draw[-, fill=green!30, opacity=.5] (2)--(6)--(9)--cycle; + \draw[-, fill=green!30, opacity=.5] (2)--(5)--(9)--cycle; + \draw[-, fill=green!30, opacity=.5] (5)--(6)--(9)--cycle; + + \draw[-, fill=orange!30, opacity=.5] (7)--(8)--(9)--cycle; + \draw[-, fill=orange!30, opacity=.5] (3)--(7)--(9)--cycle; + \draw[-, fill=orange!30, opacity=.5] (3)--(7)--(8)--cycle; + \draw[-, fill=orange!30, opacity=.5] (3)--(8)--(9)--cycle; + + \foreach \i in {0,1,2,3,4,5,6,7,8,9} + \draw[blue,fill=blue] (\i) circle (1.0pt) node [below] {}; + + \end{tikzpicture} + \begin{tikzpicture}[scale=1.3] + + \coordinate (0) at (0,0,0); + \coordinate (1) at (0,0,1); + \coordinate (2) at (1,0,0); + \coordinate (3) at (0,1,0); + \coordinate (4) at (0,0,0.5); + \coordinate (6) at (0.5,0,0); + \coordinate (7) at (0,0.5,0); + \coordinate (5) at (0.5,0.0,0.5); + \coordinate (8) at (0.0,0.5,0.5); + \coordinate (9) at (0.5,0.5,0.0); + + \draw (0) -- (1) -- (2) -- (0); + \draw (0) -- (1) -- (3) -- (0); + \draw (1) -- (2) -- (3) -- (1); + + \draw[-, fill=red!30, opacity=.5] (4)--(5)--(6)--cycle; + \draw[-, fill=red!30, opacity=.5] (4)--(5)--(8)--cycle; + \draw[-, fill=red!30, opacity=.5] (4)--(6)--(8)--cycle; + \draw[-, fill=red!30, opacity=.5] (5)--(6)--(8)--cycle; + +% \draw[-, fill=blue!30, opacity=.5] (4)--(6)--(7)--cycle; +% \draw[-, fill=blue!30, opacity=.5] (4)--(6)--(8)--cycle; +% \draw[-, fill=blue!30, opacity=.5] (4)--(7)--(8)--cycle; +% \draw[-, fill=blue!30, opacity=.5] (6)--(7)--(8)--cycle; + +% \draw[-, fill=green!30, opacity=.5] (6)--(7)--(8)--cycle; +% \draw[-, fill=green!30, opacity=.5] (6)--(7)--(9)--cycle; +% \draw[-, fill=green!30, opacity=.5] (6)--(8)--(9)--cycle; +% \draw[-, fill=green!30, opacity=.5] (7)--(8)--(9)--cycle; +% + \draw[-, fill=blue!30, opacity=.5] (5)--(6)--(8)--cycle; + \draw[-, fill=blue!30, opacity=.5] (5)--(6)--(9)--cycle; + \draw[-, fill=blue!30, opacity=.5] (5)--(8)--(9)--cycle; + \draw[-, fill=blue!30, opacity=.5] (6)--(8)--(9)--cycle; + + \foreach \i in {0,1,2,3,4,5,6,7,8,9} + \draw[blue,fill=blue] (\i) circle (1.0pt) node [below] {}; + + \end{tikzpicture} + \begin{tikzpicture}[scale=1.3] + + \coordinate (0) at (0,0,0); + \coordinate (1) at (0,0,1); + \coordinate (2) at (1,0,0); + \coordinate (3) at (0,1,0); + \coordinate (4) at (0,0,0.5); + \coordinate (6) at (0.5,0,0); + \coordinate (7) at (0,0.5,0); + \coordinate (5) at (0.5,0.0,0.5); + \coordinate (8) at (0.0,0.5,0.5); + \coordinate (9) at (0.5,0.5,0.0); + + \draw (0) -- (1) -- (2) -- (0); + \draw (0) -- (1) -- (3) -- (0); + \draw (1) -- (2) -- (3) -- (1); + +% \draw[-, fill=red!30, opacity=.5] (4)--(5)--(6)--cycle; +% \draw[-, fill=red!30, opacity=.5] (4)--(5)--(8)--cycle; +% \draw[-, fill=red!30, opacity=.5] (4)--(6)--(8)--cycle; +% \draw[-, fill=red!30, opacity=.5] (5)--(6)--(8)--cycle; + + \draw[-, fill=red!30, opacity=.5] (4)--(6)--(7)--cycle; + \draw[-, fill=red!30, opacity=.5] (4)--(6)--(8)--cycle; + \draw[-, fill=red!30, opacity=.5] (4)--(7)--(8)--cycle; + \draw[-, fill=red!30, opacity=.5] (6)--(7)--(8)--cycle; + + \draw[-, fill=blue!30, opacity=.5] (6)--(7)--(8)--cycle; + \draw[-, fill=blue!30, opacity=.5] (6)--(7)--(9)--cycle; + \draw[-, fill=blue!30, opacity=.5] (6)--(8)--(9)--cycle; + \draw[-, fill=blue!30, opacity=.5] (7)--(8)--(9)--cycle; + +% \draw[-, fill=orange!30, opacity=.5] (5)--(6)--(8)--cycle; +% \draw[-, fill=orange!30, opacity=.5] (5)--(6)--(9)--cycle; +% \draw[-, fill=orange!30, opacity=.5] (5)--(8)--(9)--cycle; +% \draw[-, fill=orange!30, opacity=.5] (6)--(8)--(9)--cycle; + + \foreach \i in {0,1,2,3,4,5,6,7,8,9} + \draw[blue,fill=blue] (\i) circle (1.0pt) node [below] {}; + + \end{tikzpicture} + + \caption{New refinement strategies for triangles and tetrahedrons: triangles + are subdivided in 4 children and tetrahedrons 8 ones.}\label{fig:refinement} + +\end{figure} +\begin{itemize} +\item Experimental support of locally refined meshes. FEM on locally refined +meshes requires 1) the possibility to locally refine the mesh (see Figure~\ref{fig:refinement}) +and 2) appropriate hanging-node constraints. For 3D, we are in progress to +implement the missing constraint definitions. +\item TODO +\end{itemize} +Furthermore, we continued to remove the usage of \texttt{GeometryInfo} from +the library and to replace the instances by more general equivalent functions, which +in many cases rely of \texttt{ReferenceCell}. Once all instance of +\texttt{GeometryInfo} are remove, we will deprecate the class. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\subsection{Topic 2} - - +\subsection{Repartitioning of distributed meshes}\label{sec:repartitioning} + +Until now, distributed meshes were either partitioned statically (\texttt{parallel::\allowbreak fullydistributed::\allowbreak Triangulation}; short \texttt{p::f::T}) or used a +fixed policy to partition the cells among processes +(\texttt{parallel::\allowbreak distributed::\allowbreak Triangulation}; short \texttt{p::d::T}). For latter, we +use a Morton-order as the backend of that class---\texttt{p4est}---does. Fixed Morton-order +might provide very good performance in terms in communication and +setup costs, but might be non-optimal when interfacing with other +libraries that have fixed partitioning, most notably a Cartesian +partitioning, themselves. + +New utility functions from the \texttt{RepartitioningPolicyTools} can be +used now to create a new \texttt{p::f::T} instances, +given a distributed triangulation (\texttt{p::f::T} or \texttt{p::d::T}) and a vector with the new owners of locally +owned cells. The workflow is shown in the following listing: +\begin{c++} +// original triangulation +parallel::distributed::Triangulation tria(comm); + +// select a partitioning policy and use it +const RepartitioningPolicyTools::Cartesian policy(tria); +const auto construction_data = TriangulationDescription::Utilities:: + create_description_from_triangulation(tria, policy.partition(tria)); + +// create the new triangulation +parallel::fullydistributed::Triangulation tria_pft(comm); +tria_pft.create_triangulation(construction_data); +\end{c++} +Instead of using one of the predefined partitioning policies, users +can write their own by implementing the \texttt{RepartitioningPolicyTools::Base} interface. Similarly to the +active level, also the multigrid levels can be repartitioned arbitrarily. + +\begin{figure} + \centering + \def\svgwidth{0.8\columnwidth} + \input{svg/repartitioning.pdf_tex} + \caption{Visualization of the repartitioning process: after + cells are assigned new ranks, each process collect sends the cells incl. + ghost cells to the new owner. There incoming cells are processed, duplicates + are removed and the local part of the triangulation is built.}\label{fig:repartitioning} +\end{figure} + +The setup process is visualized in Figure~\ref{fig:repartitioning}. First cells, incl. their +surrounding (ghost) cells and their parent cells, are collected and +sent to the new owner. On the +receiving side, the set of all cells are combined and possible duplicates +are removed. This information is enough to construct a new triangulation. +For sending/receiving, we apply consensus-based algorithms~\cite{hoefler2010scalable}, which +we introduced in the library in release 9.2~\cite{dealII92}. Consensus-based +algorithms are used also in \cite{ibanez2016pumi} for repartitioning. + +In future releases, we plan to add support for repartitioning based on distributed graph +partitioning libraries, e.g., \texttt{ParMETIS} of \texttt{Zotan}. Furthermore, we intend to extend the +\texttt{p::f::T} with adaptivity support. +With this and and the new repartitionging features, \texttt{p::f::T} +could be selfconsistent like \texttt{p::d::T}, which is an important +step towards the support of AMR also for distributed simplex and mixed meshes +(see also Subsection~\ref{sec:simplex}). + +%We would like to note that we provide a similar class also for repartitioning +%of vectors: \texttt{Noncontiguous\allowbreak Partitioner} from the +%\texttt{Utilities::MPI} namespace. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\subsection{Topic 3} +\subsection{Advances in matrix-free infrastructure}\label{sec:mf} +In the matrix-free infrastructure, we have added many new features. Most +notably: +\begin{itemize} +\item Improved support of Hessians: just like values and gradients can be +evaluated and integrated during matrix-free loops, one can do this now +also for Hessians both for cells and faces. This enables, e.g., to write +a matrix-free version of step-47, which solves the biharmonic equation with DG. +\item Cell-centric loops now also allow to access to gradients and Hessians +of neighboring cells on faces. The major obstacle here was to reorientation +of theses in the case of arbitrary orientated cells on unstructured meshes. +\item Users can now create their own cell batches, by providing \texttt{FEEvaluation::reinit()} a list of cell IDs. \texttt{FEEvaluation} +accesses the appropriate data and reshuffles mapping data accordingly on +the fly to enable vectorization over cells. The new feature is useful in many +contexts. Examples are application with sharp interfaces (e.g., two phase flow +or shock capturing) where one needs to treat cells that are ``cut'' by +the interface in a special way. A challenge is that cell batchs +might contain cut or not-cut cell, making vectorization potentially more complication. One way to deal with such cell batches it to apply masks if +the code paths do not diverge too much +(many functions of \texttt{FEEvaluation} allows this). Another way is to +categorize cells during \texttt{MatrixFree::reinit()} in such a way that mixed cell batches do not occur. However, calling \texttt{MatrixFree::reinit()} +might be too expensive if a very dynamic system is given, which requires +recatorization in each time step. Doing this on-the-fly might be a cheep alternative, even if not computationally optimal during matrix-free loops. +\end{itemize} +Besides these new features, we improved the performance of +hanging-node-constraint evaluation on the CPU. Instead of performing +quasi-dense matrix-vector multiplications~\cite{KronbichlerKormann2012}, we now use an +approach based on inplace interpolation and sumfactorization, similarly +as we already did in the GPU code~\cite{ljungkvist2017matrix}. The algorithm is described +in \cite{munch2022hn} and performance numbers are shown, indicating a reduction +of overhead of cells with hanging nodes by a factor of 10$\times$. + +Furthermore, we have performed a major restructuring of internals +of the \texttt{FEEvaluation} classes. This will enable us to add more +simply the support of new element types in the future, e.g., of +Raviart--Thomas and Nedelec elements. + + +%\begin{c++} +%additional_data.mapping_update_flags = ... | update_hessians; +%\end{c++} +% +%\begin{c++} +%FEEvaluation phi(matrix_free); +% +%phi.reinit(cell); +%phi.gather_evaluate(src, ... | EvaluationFlags::hessians); +% +%for(const auto q : phi.quadrature_point_indices()) +% phi.submit_hessian(phi.get_hessian(q), q); +% +%phi.integrate_scatter(... | EvaluationFlags::hessians, dst); +%\end{c++} +% +%... similar for faces; can be used to implement biharmonic equation (like in +%step-X) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\subsection{Topic 4} +\subsection{Advances in multigrid infrastructure}\label{sec:multigrid} + +In release 9.3~\cite{dealII93}, we added support for global coarsening multigrid in +addition to the established local smoothing infrastructure. Global +coarsening smoothens on the whole computational domain on each +multigrid level, which are obtained by coarsening the finest mesh globally. +For this purpose, we use a sequence of triangulations, on which we perform +the smoothing only on the active levels. To create the sequence of +triangulations, one can use the functions \texttt{create\_geometric\_coarsening\_sequence()} from the +\texttt{MGTransferGlobalCoarseningTools} namespace. A new version takes an +instance of \texttt{RepartitioningPolicyTools::Base} (see Subsection~\ref{sec:repartitioning}, which allow to specify the parallel +distribution of each multigrid level (in contrast to the fixed---first-child---policy in the case of local smoothing). Furthermore, we added support of block vectors, +fixed a number of limitations, and performed performance optimizations of +the transfer operator; particularly, the redundant copy from/to temporary vectors +has been eliminated and the application of hanging-node constraints are applied +efficiently the same way as in the matrix-free loops (see Subsection~\ref{sec:mf}). + +In \cite{munch2022gc}, the performance of \texttt{deal.II}'s local-smoothing and global-coarsening +infrastructure was compared for locally refined meshes. The results indicate that +the local definition of multirgrid levels might introduce load imbalances +in the case of local smoothing so that global coarsening is favorable despite +of potentially more expensive inter-grid transfers. To judge the benefit +of one approach against the other, \texttt{deal.II} provides new functions +\texttt{workload\_imbalance()} and \texttt{vertical\_communication\_efficiency()} +in the \texttt{MGTools} namespace to estimate the workload imbalance and the +vertical communication efficiency purely based on the given mesh. The publication also points out that not +all types of smoothers are applicable for global coarsening, due to the +presence of hanging-nodes, which is a motivation to add new smoother types +to \dealii. +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\subsection{CutFEM support}\label{sec:cut} +\begin{itemize} +\item new classes +\end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\subsection{Topic 5} +\subsection{Performance improvement of particle infrastructure}\label{sec:particles} + +\begin{itemize} +\item describe the new data structure +\item do we have performance numbers? +\end{itemize} @@ -258,18 +598,20 @@ can be found Many of the \dealii{} tutorial programs were revised in a variety of ways as part of this release. In addition, there are a number of new tutorial programs: \begin{itemize} -\item \texttt{TODO} TODO. - - +\item \texttt{step-82} was contributed by Andrea Bonito (Texas A\&M University) and Diane Guignard (University of Ottawa). It shows how +\dealii{} can be used to implement the +local discontinuous Galerkin (LDG) method for approximating the solution to the bi-Laplacian problem. +\item \texttt{step-85} was contributed by Simon Sticko (Uppsala University). It shows how to use the new CutFEM infrastructure to solve a Poisson +problem on a circular domain that is embedded in a Cartesian background mesh. \end{itemize} -There is also a new program in the code gallery (a collection of -user-contributed programs that often solve more complicated problems -than tutorial programs, and intended as starting points for further -research rather than as teaching tools): -\begin{itemize} -\item ``\texttt{TODO}'' TODO. -\end{itemize} +%There is also a new program in the code gallery (a collection of +%user-contributed programs that often solve more complicated problems +%than tutorial programs, and intended as starting points for further +%research rather than as teaching tools): +%\begin{itemize} +%\item ``\texttt{TODO}'' TODO. +%\end{itemize} @@ -278,15 +620,26 @@ research rather than as teaching tools): The 9.4 release includes \href{https://dealii.org/developer/doxygen/deal.II/changes_between_9_3_0_and_9_4_0.html} -{around TODO incompatible changes}; see \cite{changes94}. The majority of these changes +{around 40 incompatible changes}; see \cite{changes94}. The majority of these changes should not be visible to typical user codes; some remove previously deprecated classes and functions; and the majority change internal interfaces that are not usually used in external applications. That said, the following are worth mentioning since they may have been more widely used: \begin{itemize} - \item TODO - \item TODO + \item In continuation of our attempt to merge the classes \texttt{DoFHandler} and \texttt{hp::DoFHandler}, we have removed the + template parameter \texttt{DoFHandlerType} form many classes and + functions and replaced it by \texttt{dim}/\texttt{spacedim}. Affected + classes are, e.g., \texttt{SolutionTransfer} and \texttt{DataOut}. + \item \texttt{FE\_RaviartThomasNodal} now uses a different polynomial space to allow +for a simpler use for faces in non-standard orientation. The new polynomials +are anisotropic tensor products of Lagrange polynomials on the points of a +Gauss--Lobatto quadrature formula. This change leads to different entries in +the matrices and constraints, for example, but as the resulting polynomial +space spans the same polynomials, no change in accuracy should be expected. +\item We made different changes to the repartitoning of \texttt{parallel::distributed::Triangulation}. Most notably, we have have +removed the default weight (10,000) for consistency reasons with the rest +of the library. \end{itemize} @@ -317,7 +670,7 @@ following: \begin{multicols}{2} \vspace*{-36pt} \begin{itemize} - \item For geometric multigrid: \cite{Kanschat2004,JanssenKanschat2011,ClevengerHeisterKanschatKronbichler2019}; + \item For geometric multigrid: \cite{Kanschat2004,JanssenKanschat2011,ClevengerHeisterKanschatKronbichler2019, munch2022gc}; \item For distributed parallel computing: \cite{BangerthBursteddeHeisterKronbichler11}; \item For $hp$-adaptivity: \cite{BangerthKayserHerold2007}; \item For partition-of-unity (PUM) and finite element enrichment methods: @@ -393,9 +746,55 @@ contributed code to this release:\\ % Uwe Koecher doesn't usually show up in the changelog, but % we should make sure he's listed. % -% 9.3: updated 5/08/2021 PM -% sorted by WB 5/28 -TODO. +% 9.4: updated 23/04/2022 PM +Pasquale Africa, +Tyler Anderson, +Francesco Andreuzzi, +Mathias Anselmann, +Maximilian Bergbauer, +Bruno Blais, +Till Budde, +Fabian Castelli, +Praveen Chandrashekar, +Cu Cui, +Ivo Dravins, +Marco Feder, +Niklas Fehn, +Johannes Friedlein, +Sebastian Fuchs, +Rene Gassmoeller, +Nicola Giuliani, +Alexander Grayver, +Diane Guignard, +Jake Harmon, +Sean Ingimarson, +Pengfei Jia, +Sebastian Kinnewig, +Simon Konrad, +Katharina Kormann, +Paras Kumar, +Wenyu Lei, +Alberto F. Martin, +Nils Much, +Lucas Myers, +Justin O'Connor, +Judith Pauen, +Vachan Potluri, +Raghunandan Pratoori, +Sebastian Proell, +Ce Qin, +Reza Rastak, +Jose E. Roman, +Raphael Schoof, +Magdalena Schreter, +Konrad Simon, +Simon Sticko, +Bruno Turcksin, +Kuljit S. Virk, +Michał Wichrowski, +Niklas Wik, +Jiaqi Zhang. + Their contributions are much appreciated! diff --git a/9.4/svg/repartitioning.pdf_tex b/9.4/svg/repartitioning.pdf_tex new file mode 100644 index 0000000..2ce793e --- /dev/null +++ b/9.4/svg/repartitioning.pdf_tex @@ -0,0 +1,72 @@ +%% Creator: Inkscape 1.1.2 (1:1.1+202202050942+0a00cf5339), www.inkscape.org +%% PDF/EPS/PS + LaTeX output extension by Johan Engelen, 2010 +%% Accompanies image file 'repartitioning.pdf' (pdf, eps, ps) +%% +%% To include the image in your LaTeX document, write +%% \input{.pdf_tex} +%% instead of +%% \includegraphics{.pdf} +%% To scale the image, write +%% \def\svgwidth{} +%% \input{.pdf_tex} +%% instead of +%% \includegraphics[width=]{.pdf} +%% +%% Images with a different path to the parent latex file can +%% be accessed with the `import' package (which may need to be +%% installed) using +%% \usepackage{import} +%% in the preamble, and then including the image with +%% \import{}{.pdf_tex} +%% Alternatively, one can specify +%% \graphicspath{{/}} +%% +%% For more information, please see info/svg-inkscape on CTAN: +%% http://tug.ctan.org/tex-archive/info/svg-inkscape +%% +\begingroup% + \makeatletter% + \providecommand\color[2][]{% + \errmessage{(Inkscape) Color is used for the text in Inkscape, but the package 'color.sty' is not loaded}% + \renewcommand\color[2][]{}% + }% + \providecommand\transparent[1]{% + \errmessage{(Inkscape) Transparency is used (non-zero) for the text in Inkscape, but the package 'transparent.sty' is not loaded}% + \renewcommand\transparent[1]{}% + }% + \providecommand\rotatebox[2]{#2}% + \newcommand*\fsize{\dimexpr\f@size pt\relax}% + \newcommand*\lineheight[1]{\fontsize{\fsize}{#1\fsize}\selectfont}% + \ifx\svgwidth\undefined% + \setlength{\unitlength}{684.71485517bp}% + \ifx\svgscale\undefined% + \relax% + \else% + \setlength{\unitlength}{\unitlength * \real{\svgscale}}% + \fi% + \else% + \setlength{\unitlength}{\svgwidth}% + \fi% + \global\let\svgwidth\undefined% + \global\let\svgscale\undefined% + \makeatother% + \begin{picture}(1,0.45602588)% + \lineheight{1}% + \setlength\tabcolsep{0pt}% + \put(0,0){\includegraphics[width=\unitlength,page=1]{repartitioning.pdf}}% + \put(0.88363077,0.05285442){\color[rgb]{0,0,0}\makebox(0,0)[lt]{\lineheight{1.25}\smash{\begin{tabular}[t]{l}\tiny 0\end{tabular}}}}% + \put(0.91134681,0.05285442){\color[rgb]{0,0,0}\makebox(0,0)[lt]{\lineheight{1.25}\smash{\begin{tabular}[t]{l}\tiny 1\end{tabular}}}}% + \put(0.9388259,0.05285442){\color[rgb]{0,0,0}\makebox(0,0)[lt]{\lineheight{1.25}\smash{\begin{tabular}[t]{l}\tiny 2\end{tabular}}}}% + \put(0.96654194,0.05285442){\color[rgb]{0,0,0}\makebox(0,0)[lt]{\lineheight{1.25}\smash{\begin{tabular}[t]{l}\tiny 3\end{tabular}}}}% + \put(0.86106546,0.05285442){\color[rgb]{0,0,0}\makebox(0,0)[rt]{\lineheight{1.25}\smash{\begin{tabular}[t]{r}\tiny{ranks:}\end{tabular}}}}% + \put(0,0){\includegraphics[width=\unitlength,page=2]{repartitioning.pdf}}% + \put(0.0907548,0.44492978){\color[rgb]{0,0,0}\makebox(0,0)[t]{\lineheight{1.25}\smash{\begin{tabular}[t]{c}\textit{old partitioning}\end{tabular}}}}% + \put(0.09075479,0.00303788){\color[rgb]{0,0,0}\makebox(0,0)[t]{\lineheight{1.25}\smash{\begin{tabular}[t]{c}\textit{new partitioning}\end{tabular}}}}% + \put(0,0){\includegraphics[width=\unitlength,page=3]{repartitioning.pdf}}% + \put(0.36459141,0.44492978){\color[rgb]{0,0,0}\makebox(0,0)[t]{\lineheight{1.25}\smash{\begin{tabular}[t]{c}\textit{old rank "0"}\end{tabular}}}}% + \put(0.36459141,0.00303788){\color[rgb]{0,0,0}\makebox(0,0)[t]{\lineheight{1.25}\smash{\begin{tabular}[t]{c}\textit{old rank "1"}\end{tabular}}}}% + \put(0,0){\includegraphics[width=\unitlength,page=4]{repartitioning.pdf}}% + \put(0.9133016,0.22778746){\color[rgb]{0,0,0}\makebox(0,0)[t]{\lineheight{1.25}\smash{\begin{tabular}[t]{c}\textit{new rank "0"}\end{tabular}}}}% + \put(0,0){\includegraphics[width=\unitlength,page=5]{repartitioning.pdf}}% + \end{picture}% +\endgroup% diff --git a/9.4/svg/repartitioning.svg b/9.4/svg/repartitioning.svg new file mode 100644 index 0000000..fae03c8 --- /dev/null +++ b/9.4/svg/repartitioning.svg @@ -0,0 +1,976 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + \tiny 0 + \tiny 1 + \tiny 2 + \tiny 3 + \tiny{ranks:} + + + + + + + + + + + + + + + + + + \textit{old partitioning} + \textit{new partitioning} + + + + + + + + + + + + + + + + + + + + + + + + + + + + + \textit{old rank "0"} + \textit{old rank "1"} + + + + + + + + + + + + + + + \textit{new rank "0"} + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + -- 2.39.5