Today, Discuss.io announced the Pulse program, a new solution to help reduce the friction of building a consumer empathy program, Discuss.io's Pulse program makes it possible for every marketer to talk to consumers frequently. It is another industry first – a packaged solution that operationalizes consumer empathy quickly, easily, and at scale. There is now a solution that enables every marketer to talk global consumers on a regular basis.
Great marketers know that understanding consumers is the key to building products that people want to buy and creating advertising that resonates. And in the age of big data, there is no lack of analytics tools and platforms that help build that understanding, but there is no technology that can replace the understanding and empathy that can be developed from a live conversation with a consumer.
Discuss.io's Pulse program enables live video conversations directly between consumers and marketers. Regular conversations with global consumers can be scaled across geographies and teams enabling all marketers within an organization to build and strengthen consumer empathy.
Discuss.io's Pulse program is available today. Within days, consumers can be available for live video conversations. To arrange a conversation or learn more, please contact the Discuss.io team HERE.
Link to press release here.


The first in a new range of classic Doctor Who soundtracks will be released next week by Silva Screen Records, delving back to the end of the Fifth's Doctor's era with Roger Limb's score for The Caves of Androzani.
In 1984-5 we had new tools at our disposal including the Fairlight Computer Music Instrument (CMI) which I used to create the rhythmic percussion figures, and the wonderfully versatile Yamaha DX7 which was a landmark in the development of the synthesiser. I'd read the scripts but it was only when I saw the edited episodes on VHS that my ideas started to take shape. The greatest slice of luck was having Graeme Harper as director. He was able to explain exactly what he wanted from me, a great advantage!
Roger Limb was part of the BBC Radiophonic Workshop team which he joined in 1972. Perhaps best known for his work on Doctor Who, from 1981 to 1985, Limb composed the music for the The Keeper of Traken, Four to Doomsday, Black Orchid, Time-Flight, Arc of Infinity, Terminus, The Caves of Androzani and Revelation of the Daleks. In the 80s and 90s Limb has contributed music to a number of television series including The Justice Game, Aliens in the Family, Thinkabout, The Box of Delights, Kevin and Co, Martin Luther: Heretic, Storytime and Look and Read. He is also known for the now cult "Swirley" tune, a happy piece of electronic music that was used as the theme to the BBC's Service Information news bulletins in the late 70s and early 80s.
The DVD isolated scores are straight off the original tapes (resync'd-mono, but and also quite heavily compressed as per the original transmission so as to level match the soundtracks). There is little attempt at remastering, and the AC3 encoding on the DVD is similar to MP3, so lossy. The CD soundtracks are fully remastered (de-noising etc.), maintaining the greater dynamics of the original masters, and in "stereo". They all also feature (where possible and appropriate) additional and/or alternative cues.
The presentation is entirely different - the DVD isolated scores are designed for educational purposes, really (so that the viewer can see how the composer works to picture, but without the dialogue and effects getting in the way!); the CDs are presented at the highest quality for listening purposes.
Additionally, in some cases to come I have found better tapes since we did the DVDs.
The Caves of Androzani is released on the 25th March 2013 and is available for pre-order.
The Caves of Androzani was Graeme Harper's (credited) directorial debut for Doctor Who - which is the most recent broadcast episode to date that he has been credited as director?
Send your answers to this email address with the subject "curiousity has always been my downfall", along with your name and address. The competition is open worldwide, and the closing date is the 31st March 2013.


DTS1011: Features: -Inside tamper-proof hinges. Simple programmable electronic lock with buzzer and LED, 3 to 8 numbers.
Pre-drilled holes inside the safe with fixing bolts allowing anchoring. Slot is 8.75'' x 1.25'' on top of safe. Includes: -Opens with secret PIN code or included keys (2 free keys).
Construction: -Constructed of extra thick 11 gauge solid steel. Specifications: -Runs on AASIZE(1.5V) batteries.
Dimensions: -External Dimensions: 30.5'' H x 14.5'' W x 14'' D, plus 1'' for hardware depth. Internal Dimensions (top): 10'' H x 14'' W x 13'' D. Internal Dimensions (bottom): 20'' H x 14'' W x 13'' D.
The item "New Home Office Digital Deluxe Double Depository Safe Tamper Proof Security Lock" is in sale since Monday, May 29, 2017. This item is in the category "Home & Garden\Home Improvement\Home Security\Safes".
The seller is "phoenixonlinemall" and is located in Little River, South Carolina. This item can be shipped to United States, Russian federation.


Genetic diseases can be very serious, and even life threatening. Unfortunately, with most genetic diseases, we simply do not have the science available as of yet to prevent those diseases from passing along family lines. Cystic Fibrosis is one such genetic disease, but there is hope in the form of cystic fibrosis gene therapy.
Cystic Fibrosis is a disease which is inherited through the genes, and overall, it has a negative effect on the whole body. Most people who have Cystic Fibrosis, also known as CF and as Sixty Five Roses to children who cannot properly announce the name of the disease, will suffer progressive disability. Early death is also a part of CF.
When a person has CF, they have cysts in the pancreas, and often have difficulty breathing due to infections in the lungs. These are the two most serious effects of the disease. Other symptoms include frequent sinus infections, diarrhea, slow growth, and infertility.
What is Cystic Fibrosis Gene Therapy?
To understand cystic fibrosis gene therapy, you must first consider what gene therapy is overall. For gene therapy, genes are actually injected into the person's tissues. There are two types of gene therapy. The first is Germ Line Gene Therapy and the second is Somatic Gene Therapy. Cystic Fibrosis Gene Therapy is Somatic Gene Therapy.
What are the Latest Cystic Fibrosis Gene Therapy Developments?
In March of 1999, it was reported that gene therapy had the ability to improve one of the problems associated with cystic fibrosis. Fortunately, this was not the first breakthrough in this field, or the last.
Gene therapy first came into discussion in 1972, when it was first mentioned in a medical journal. Gene therapy was not approved in the United States, however, until 1990. In 2002, it was widely reported that there were dangers to this type of treatment, when some patients developed health problems that resembled leukemia. Despite this, the treatment was still used and improvements were made.
Unfortunately, in the case of cystic fibrosis, gene therapy may only be a temporary solution to a lifelong problem. It doesn't always work, and when it does work, the results are not long term. The same is true, thus far, for all other health problems that gene therapy is used for.
It is also important to note that gene therapy works best for conditions that are caused by mutation of a single gene, as opposed to problems that are caused by the mutation of multiple genes, which is the case for cystic fibrosis.


We seek to empower girls by developing their knowledge and competences in computational thinking.
"Patrones Hermosos" or "Beautiful Patterns" is a program to develop Computational Thinking skills on Latin American girls between 13 and 17 years of age, motivating them towards STEM careers.
This initiative is led by Abel Sanchez PhD, director of research and director of MIT Geospatial Laboratory. Professor Sanchez took the program for the first time to Nuevo Leon on 2017 and run a pilot of 2 weeks with 50 participants.
Due to the success of this workshop, the program is being extended to more than 11 states in Mexico the objective in 2019 is to impact more than 1,500 girls.
The website http://dreamers.mit.edu includes a complete description, as well as proof of its application in 2017 and 2018.
Your donation allows us, mainly, to pay for the flights of the instructors of the MIT, but also to transport girls of remote zones, the materials, the foods, the workshops that take place from 9 to 4 pm, from Monday to Friday, this Year from May 27 to 31.
The previous topics practice algorithms such as the Gale-Shapley algorithm (Nobel prize winner), ciphering, bubble sorting, algorithm for Towers of Hanoi, binary counting and even block-chain.
During the day the participants look at every topic in different ways: lecture, practical exercise, team presentation of the topic applying the algorithm to problems of their own life, playing games and competing against their peers (going through the algorithm), programming the algorithm, etc. Throughout the week they work in teams on a project that is presented on Friday, mainly through web pages they design and construct.
The last activity gives a one to one time with all the instructors, all of them engineering or computer science students, no much older than the participants. During this chat the younger girls hear what is to be a CS or engineering student, in their own language.
Our main challenge is to obtain the funds for the flights of the MIT girls. Despite the support of the Tec, the MIT, Csoftmty and other universities as UDEM, UERRE, UANL, UP, UT, Tec Milenio, Universidad de Veracruz, LANIA, Softtek, Motorola and other organizations with which we have been able to obtain laboratories for workshops, materials and food for girls, we have not yet been able to cover the most expensive flights.
In addition, there are girls outside the urban areas who wish to attend and we need to raise funds to pay for their transportation.
Check out our photos and videos, watch how girls have fun, learn advanced topics and believe in themselves.
Congratulations!! great job, my admiration and respect for you.
Para empoderar a las mujeres, tenemos que unirnos y apoyarlas. Felicidades a Patrones Hermosos por este programa!
Recognized as the premium sponsor, with highest priority branding.Advance logo recognition on official website homepage and sponsor section, with web link.Logo included in promotional adverts and other media outputs.Logo placed in a visually dominant position in the T-Shirt distributed national wide.Space to display marketing material in lunching or closing event.Space for content on digital goodie bag.Promotion to media and press outlets as a major supporter of the program.Acknowledgment in video 2019.
Recognized as sponsor, with high priority branding.Advance logo recognition on official website homepage and sponsor section, with web link.Logo included in promotional adverts and other media outputs.Logo placed in a visually dominant position in the T-Shirt distributed national wide (second after Diamond Sponsors).Space to display marketing material in lunching or closing event.Space for content on digital goodie bag.Promotion to media and press outlets as a supporter of the program.Acknowledgment in video 2019.
Recognized as sponsor on official website homepage sponsor section, with web link.Logo placed in T-Shirt distributed national wide.Space for content on digital goodie bag.Promotion on social networks as a supporter of the program.Acknowledgment in video 2019.
Letter of appreciation from Abel Sanchez and Beautiful Patterns.Promotion on social networks as a supporter of the program.


Hodder is nine. He lives on his own with his dad, who puts up posters at night for a living. One night a fairy tells Hodder to save the world. But how do you mount an expedition if you've no pals? An affectionate, amusing, magical tale that goes straight to the heart.


National Initiative for Developing and Harnessing Innovations (NIDHI) is an umbrella programme conceived and developed by the Department of Science & Technology (DST), Government of India, for nurturing ideas and innovations (knowledge-based and technology-driven) into successful start-ups.
Under this initiative, DST has launched NIDHI- Promoting and Accelerating Young and ASpiring innovators & startups (NIDHI-PRAYAS) program. The program caters to idea-stage entrepreneurs with a physical product offering, who require support for prototyping. It would also facilitate the innovators with the Physical infrastructure, Technical Guidance, Business Mentorship etc.
Enable translation of an innovative idea to a prototype.
Provide a platform for faster experimentation and modify approaches in the idea to market journey.
Generate innovative solutions relevant to the local and global problems.
A pre-incubation program or pipeline activity leading to startup incubation. Ideal end point is venture creation and development.


Zurich Professional Liability Insurance offers individual insurance coverage solutions for self-employed professionals. Thanks to the expertise of our specialists in Switzerland, lawyers, fiduciaries and management consultants and their employees are fully protected against claims for damages.
Working as a self-employed lawyer, fiduciary or consultant entails very specific risks. With Zurich Professional Liability Insurance, you don't have to worry about third-party claims for damages. Zurich covers you, your partners and your staff with individually tailored solutions.
All of Zurich's professional liability insurance solutions give you a free choice of additional coverage – such as legal protection in criminal, supervisory and administrative proceedings; coverage for board of directors positions held at outside entities (D&O); waiver of gross negligence; waiver of the right to terminate in the event of a claim.
You can combine basic and additional insurance coverage to fit your individual needs and services. Suitable solutions are summarized for legal professions, fiduciaries or management consultants below.
Additional coverage for liquidation activities in line with the Swiss Code of Obligations/Swiss Civil Code is the optimal supplement to the basic insurance cover.
If you work in the fiduciary field, it is worthwhile insuring against claims for damages. Zurich Professional Liability Insurance is designed for a range of activities and services in your field, such as fiduciaries, accountants, tax advisors, real estate managers, asset managers or FINMA-licensed distributors of investment fund units and representatives of foreign collective investment schemes.
Additional coverage for liquidation activities in line with the Swiss Code of Obligations/Swiss Civil Code is the optimal supplement to the basic insurance coverage.
Zurich Professional Liability Insurance for management consultants meets the quality standards of the Association of Management Consultants Switzerland (ASCO). Also, ASCO members can take out Zurich insurances at preferential terms.
Effective protection against claims for compensation. We would be glad to advise you.
Find your ideal BVG solution quickly and easily with Switzerland's first online calculator.
Loss of earnings, hospital stays, disability – accident insurance for the self-employed protects you against unpleasant surprises.


The Dynamic Laws of Prosperity: Lectures is the companion to the Catherine Ponder classic. In these lectures, Ponder personally guides you step by step through the Dynamic Laws of Prosperity. Bathe yourself in prosperity ideas by listening at work, in your car, or while exercising. These lectures are a must for Catherine Ponder fans.


text:
\section{Introduction}

Balanced $k$-way hypergraph partitioning (HGP) is a classical, well-studied optimization problem, whose goal is to divide the vertices of a hypergraph into $k$ blocks of bounded size while minimizing an objective function on hyperedges that connect two or more blocks.
A commonly used objective function is the \emph{connectivity metric}, which aims to minimize the number of blocks connected by a hyperedge.
HGP has applications in various domains such as VLSI design~\cite{ALPERT-SURVEY}, scientific computing~\cite{PATOH}, storage sharding for distributed databases~\cite{schism, SHP}, and hypergraph processing frameworks for network analysis~\cite{hg-processing-framework-MESH, hg-processing-hyperx}.
Generally speaking, it can be used to accurately optimize data or workload distribution for distributed computer systems with limited memory and expensive communication.
Since hypergraph partitioning is NP-hard~\cite{LENGAUER}, most state-of-the-art partitioners use heuristic \emph{multilevel} algorithms~\cite{HENDRICKSON}.

These algorithms create a hierarchy of successively smaller and structurally similar hypergraphs by \emph{contracting} pairs or clusters of vertices (\emph{coarsening} phase).
Once the coarsest hypergraph is small enough, an \emph{initial partition} is computed.
Subsequently, the contractions are reverted level-by-level, and, on each level, \emph{local search} heuristics are used to improve the partition from the previous level (\emph{refinement phase}), e.g. using the classical FM algorithm~\cite{FM} or simple greedy heuristics~\cite{HMETIS-K}.

In recent years, problem sizes have grown beyond what full-fledged multilevel single-threaded codes can handle in reasonable time.
This resulted in very fast and simple algorithms that avoid the multilevel framework but yield solutions of inferior quality~\cite{TheHypeIsOver}.
As solution quality directly impacts the scalability of the application this seems to be a bad trade-off.
Hence, parallelization of the components of the multilevel framework is an important avenue for research.
Most of the work on parallelization has focused on distributed-memory systems~\cite{ZOLTAN, PARKWAY-2}.
However, shared-memory systems offer more algorithmic options, so that solution quality will be closer to the highly-tuned sequential codes.

\paragraph{Contribution.}

In this work, we present our shared-memory parallel multilevel hypergraph partitioning system \texttt{Mt-KaHyPar} that is able to partition hypergraphs with billions of pins in a matter of minutes.
To the best of our knowledge, it is the first shared-memory parallel hypergraph partitioner, and the first partitioner to implement fully-parallel direct k-way FM refinement~\cite{FM}.
We contribute parallel implementations of a clustering algorithm for coarsening, an efficient parallel contraction algorithm, a community detection algorithm to guide the coarsening, initial partitioning via recursive bipartitioning with work-stealing, a number of techniques to maintain and verify gains in parallel, as well as a scalable label propagation refinement algorithm~\cite{HMETIS-K}.
Our gain calculation techniques include an exact gain recalculation algorithm that allows for parallelizing a step of the FM algorithm that was previously deemed inherently sequential~\cite{MT-METIS-REFINEMENT}.
The algorithms are implemented using the parallel primitives of Intel's TBB library to leverage work stealing in all stages.

\paragraph{Results.}
\texttt{Mt-KaHyPar} achieves good speedups -- up to a factor of 51 on a machine with 64 cores and a harmonic mean speedup of $23.5$.
It provides similar quality as the fastest sequential partitioner \texttt{PaToH}~\cite{PATOH} in its quality preset and has similar average running time as \texttt{PaToH}'s default preset when using 10 cores of a 20-core machine.
Further, it is much faster than the high-quality sequential partitioners \texttt{hMetis}~\cite{HMETIS-K, HMETIS}~and \kahyparnocite~\cite{KAHYPAR-K, KAHYPAR-MF, KAHYPAR-CA}~and produces solutions of similar quality when given the same running time for additional repetitions.
On a second benchmark set with larger instances, it produces better solutions than the distributed hypergraph partitioner \texttt{Zoltan}~\cite{ZOLTAN}~on 95\% of the instances, while still being a factor of 2.1 faster, when both use 64 cores.
It is even slightly faster than \texttt{PaToH}'s default preset with just 4 cores on these larger instances and produces partitions with higher quality on 83\% of the instances.

\paragraph{Outline.}
Our paper is structured according to the different phases of the multilevel framework.
We introduce notation in Section~\ref{sec:preliminaries} and discuss related work in Section~\ref{sec:related_work}.
Subsequently, we describe our coarsening algorithm in Section~\ref{sec:coarsening}, initial partitioning in Section~\ref{sec:initial_partitioning}, various gain calculation techniques in Section~\ref{sec:gains}, as well as our refinement algorithms in Sections~\ref{sec:label-propagation} - \ref{sec:rebalancing}.
Additionally, we describe engineering aspects in Section~\ref{sec:details}, before discussing our extensive experimental evaluation in Section~\ref{sec:experiments} and presenting future work in Section~\ref{sec:conclusion}.

\section{Preliminaries}\label{sec:preliminaries}

A \emph{weighted hypergraph} $H=(V,E,c,\omega)$ is defined as a set of vertices $V$ and a set of hyperedges/nets $E$ with vertex weights $c:V \to \mathbb{R}_{>0}$ and net weights $\omega:E \to \mathbb{R}_{>0}$, where each net $e$ is a subset of the vertex set $V$ (i.e., $e \subseteq V$).
The vertices of a net are called its \emph{pins}.
We extend $c$ and $\omega$ to sets in the natural way, i.e., $c(U) :=\sum_{v\in U} c(v)$ and $\omega(F) :=\sum_{e \in F} \omega(e)$.
A vertex $v$ is \emph{incident} to a net $e$ if $v \in e$.
$\mathrm{I}(v)$ denotes the set of all incident nets of $v$.
The \emph{degree} of a vertex $v$ is $d(v) := |\mathrm{I}(v)|$.
The \emph{size} $|e|$ of a net $e$ is the number of its pins.
We call two nets $e_i$ and $e_j$ with different identifiers $i \neq j$ \emph{identical} if they have the same pins $e_i = e_j$.

A \emph{$k$-way partition} of a hypergraph $H$ is a surjective function $\Partition : V \to \{1, \dots, k\}$.
The blocks $V_i := \Partition^{-1}(i)$ of $\Partition$ are the inverse images.
A $2$-way partition is also called a \emph{bipartition}.
We call $\Partition$ \emph{$\varepsilon$-balanced} if each block $V_i$ satisfies the \emph{balance constraint}: $c(V_i) \leq L_{\max} := (1+\varepsilon)\lceil \frac{c(V)}{k} \rceil$ for some parameter $\mathrm{\varepsilon} \in (0,1)$.
The \emph{balanced $k$-way hypergraph partitioning problem} (HGP) asks for an $\varepsilon$-balanced $k$-way partition of $H$.

For each net $e$, $\ensuremath{\Lambda}(e) := \{V_i \mid  V_i \cap e \neq \emptyset\}$ denotes the \emph{connectivity set} of $e$.
The \emph{connectivity} $\ensuremath{\lambda}(e)$ of a net $e$ is the cardinality of its connectivity set, i.e., $\ensuremath{\lambda}(e) := |\ensuremath{\Lambda}(e)|$.
A net is called a \emph{cut net} if $\ensuremath{\lambda}(e) > 1$, otherwise  (i.e., if $|\mathrm{\lambda}(e)|=1$) it is called an \emph{internal} net.
A vertex $u$ that is incident to at least one cut net is called a \emph{boundary vertex}.
The number of pins of a net $e$ in block $V_i$ is denoted by $\ensuremath{\mathrm{\Phi}}(e,V_i) := |\{V_i \cap e \}|$.

In this paper we focus on the \emph{connectivity metric} $(\lambda - 1)(\Pi) := \sum_{e \in E} (\lambda(e) - 1) \: \omega(e)$.
Given a partition $\Partition$, moving $u$ from its block $\Partition(u)$ to $V_j$ improves the connectivity metric by $\omega(\{ e \in I(u) \mid \ensuremath{\mathrm{\Phi}}(e, \Partition(u)) = 1 \}) - \omega(\{e \in I(u) \mid \ensuremath{\mathrm{\Phi}}(e, V_j) = 0 \})$.
This term is called the \emph{gain} of the move.

\section{Related Work}
\label{sec:related_work}

\input{sections/related_work}

\section{Coarsening}\label{sec:coarsening}
\input{sections/coarsening}

\section{Initial Partitioning}\label{sec:initial_partitioning}
\input{sections/initial_partitioning}

\input{sections/refinement}

\section{Engineering Aspects}\label{sec:details}
\input{sections/details}

\section{Experiments}\label{sec:experiments}

\input{sections/experiments}

\section{Conclusion and Future Work}\label{sec:conclusion}

We propose a shared-memory multilevel hypergraph partitioning algorithm that guarantees balanced solutions and exhibits good speedups and solution quality, even compared with sequential algorithms.
This is achieved by carefully parallelizing and engineering each phase of the multilevel framework.
To further improve solution quality, future work includes parallelizing flow-based refinement techniques~\cite{REBAHFC, KAHYPAR-HFC, KAHYPAR-MF} as well as KaHyPar's n-level hierarchy approach~\cite{KAHYPAR-K, KaHyPar-R}.
Additionally, we want to speed up our FM implementation, and improve the solution quality of label propagation, e.g., using hill-scanning~\cite{MT-METIS-REFINEMENT} or caching negative gain moves to enable otherwise infeasible high-gain moves.
Finally, our parallel gain recalculation can replace the sequential recalculation in the parallel graph partitioner \texttt{Mt-KaHIP}.

\printbibliography

\subsection{Clustering.}\label{sec:coarsening:clustering}

Initially each vertex is in its own cluster.
We iterate over the vertices in random order in parallel.
For each vertex $u$ we compute the best cluster $\mathcal{C}$ to join according to the \emph{heavy-edge} rating function~\cite{PATOH,KAHYPAR-CA,HMETIS}
\[r(u, \mathcal{C}) := \sum_{e \in I(u) \cap I(\mathcal{C})} \frac{\omega{(e)}}{|e| - 1},\]
which prefers clusters that share a large number of heavy nets of small size with $u$.
Additionally, $\mathcal{C}$ must fulfill a weight constraint $c(\mathcal{C}) \leq \lceil \frac{c(V)}{160\cdot k} \rceil$ to ensure that a balanced partition exists.

Each vertex can be in one of three states: \emph{singleton}, currently \emph{joining} a cluster, or part of a \emph{multi-vertex cluster}.
We use compare-and-swap instructions to ensure consistency of vertex states and fetch-and-add instructions for cluster weights.
If vertex $u$ is in a singleton cluster, we find a cluster $\mathcal{C}$ for $u$ to join, and atomically set the state of $u$ to joining.
The join operation succeeds directly if $\mathcal{C}$ is a multi-vertex cluster.
Otherwise, if $\mathcal{C}$ is a singleton, we try to atomically change the state of the vertex $v$ in $\mathcal{C}$ to joining.
If that succeeds, $u$ joins $\mathcal{C}$ and both $u$ and $v$ are marked as part of a multi-vertex cluster.
In the case that $v$ is currently trying to join some cluster, we spin in a busy-waiting loop until the state of $v$ is updated to multi-vertex cluster by some other thread, and then join its new multi-vertex cluster.
In that loop, we check if $u$ is part of a cycle of vertices trying to join each other.
If so, the vertex with the smallest ID in the cycle gets to join its desired cluster, thus breaking the cycle.

We proceed to the contraction phase after one pass over the vertices or as soon as the current clustering reduces the number of vertices by more than a factor of $2.5$.
The weight constraint on coarse vertices can lead to passes in which only few vertices are contracted.
If a pass reduces the number of vertices by less than a factor of $1.01$, we still perform the remaining contraction and then proceed to initial partitioning, even if the $160 \cdot k$ vertex limit is not reached.

\subsection{Contraction.}

Contracting vertex clusters into a coarser hypergraph consists of several steps.
First, we remap cluster IDs to a consecutive range by computing a parallel prefix sum on an array that has a one at position $i$ if $i$ is a used cluster ID and zero otherwise.
Then, we accumulate the weights of vertices in each cluster using atomic fetch-and-add instructions.
Subsequently, we map the pins of each net to their cluster IDs, and remove duplicate pins by sorting the remapped pins of each net and keeping only the first occurrence of a vertex.
Furthermore, we remove nets with a single pin and replace multiple identical nets by a single net with aggregated weight.
Finally, we construct two adjacency arrays used to iterate over pins and incident nets, by computing parallel prefix sums over the sizes of the remaining nets (resp. degrees)..

For identical net detection we parallelize the \textsc{InrSrt} algorithm of Aykanat et al.~\cite{INR-Source, INR}.
It uses \emph{fingerprints} $\sum_{v \in e} v^2$ to eliminate unnecessary pairwise comparisons between nets.
Nets with different fingerprints or different sizes cannot be identical.
We distribute the fingerprints and their associated nets to the threads using a hash function.
Each thread sorts the nets by their fingerprint and size and then performs pairwise comparisons on the subranges of potentially identical nets.
We aggregate the weights of identical nets at a representative and mark the others as invalid.
We skip comparisons with invalidated nets.

\subsection{Community Detection Enhancement.}

We enhance the coarsening process by prohibiting contractions between sparsely connected vertices of the hypergraph.
\texttt{KaHyPar}~\cite{KAHYPAR-CA} uses community detection on the bipartite graph representation of the hypergraph~\cite{BIPARTITE-GRAPH-2} to identify \emph{densely connected} vertex clusters.
Contractions are then only allowed between vertices in the same cluster.
This substantially improves the quality of both the initial and the final partition.
We use the parallel Louvain method (PLM) of Staudt and Meyerhenke~\cite{Louvain, PARALLEL-LOUVAIN} for modularity maximization, which is a widely used objective function for community detection~\cite{modularity.np, Newman04}.
Initially, each vertex is in its own cluster.
PLM iterates in parallel over the vertices.
A vertex is moved to a cluster in its neighborhood with the highest positive modularity improvement.
This is repeated for up to 5 rounds or until less than 1\% of the vertices were moved in a round.
If any vertex was moved, the process is repeated on the graph obtained from contracting the clusters.

\subsection{Memory Allocation.}

Memory allocations are a significant bottleneck, which is why we implement a custom memory pool.
We estimate the memory needed by our data structures, categorized by the stage in the multilevel algorithm, and then allocate for the peak memory usage across all stages.
At the end of a stage, we pass the memory along to the next stage, and initialize data structures in parallel.
Further, we use the TBB scalable allocator~\cite{TBB} for concurrent memory allocations

\subsection{Rating Aggregation.}
For community detection and coarsening, we aggregate ratings for neighboring clusters of each vertex.
This is traditionally done with a vector of size $|V|$.
Cache friendliness (on non-shared caches) is fundamental since the bandwidth to main memory is shared between threads.
We use fixed-capacity linear probing hash tables, and resort to the vector if the expected fill ratio exceeds $\frac{1}{3}$ of the capacity.
We conservatively estimate the fill grade as the vertex degree for community detection, and as the sum of the sizes of incident nets for coarsening.

\subsection{Random Shuffling.}
For community detection and coarsening, we visit vertices in a random order.
We use a block-shuffling scheme that does not guarantee uniform randomness but suffices for our purposes.
We divide the array into $2p$ equally-sized blocks.
Each thread swaps two random blocks and shuffles them.

\subsection{FM -- Boundary Vertices.}
We iterate in parallel over all vertices to collect boundary vertices in a shared task queue consisting of thread-local vectors.
To randomize the order in which vertices are polled from the task queue, each thread shuffles its local vector.
Additionally, we use a \texttt{tbb::concurrent\_queue} to reinsert vertices that were not moved at the end of a localized search.
We only reinsert vertices that were polled from the task queue by another thread (which obviously could not claim ownership).
To find starting vertices, each thread first polls its local vector, then the \texttt{tbb::concurrent\_queue}, and then tries to steal from other threads.

\section{Parallel Gain Calculation}\label{sec:gains}

Because vertices are moved simultaneously it is inherently difficult for parallel partitioners to compute exact gain values.
For example, the gain of a vertex move can change between its initial calculation and the actual execution of the move.
Similarly, two simultaneous moves can worsen the solution quality, even if each individual gain suggested an improvement~\cite{MT-METIS}.
Our refinement algorithms have different requirements for calculating and verifying gains, depending on whether vertices are immediately moved as they are explored (label propagation, see Section~\ref{sec:label-propagation}) or not (FM, Section~\ref{sec:fm}).
In the following, we describe a technique named \emph{attributed gains} to track the overall improvement and double-check the gain of a move (label propagation), a parallel \emph{gain cache} (FM), and a novel algorithm for \emph{recomputing exact gains} of a move sequence in parallel (FM).

\texttt{Mt-KaHyPar}~optimizes the connectivity metric $\sum_{e \in E} (\ensuremath{\lambda}(e) -1 ) \: \omega(e)$.
The gain $g_i(u)$ of moving vertex $u$ to block $V_i$ can be written as
\vspace{-0.15cm}
\begin{align*}
g_i(u) = b(u) - p_i(u) \\
b(u) := \omega(\{ e \in I(u) \mid \ensuremath{\mathrm{\Phi}}(e, \Partition(u)) = 1 \}) \\
p_i(u) := \omega(\{ e \in I(u) \mid \ensuremath{\mathrm{\Phi}}(e, V_i) = 0\}).
\end{align*}

A straightforward approach to calculate $g_i(u)$ would be to iterate over all incident nets $e \in E$, increase the gain by $\omega(e)$ if $\ensuremath{\mathrm{\Phi}}(e, \Partition(u)) = 1$, and decrease it by $\omega(e)$ if $\ensuremath{\mathrm{\Phi}}(e, V_i) = 0$.

\subsection{Data Structures for Gain Calculation.}

In our partition data structure we store and maintain the pin counts $\ensuremath{\mathrm{\Phi}}(e,V_i)$ and connectivity sets $\ensuremath{\Lambda}(e)$ for each net $e$ and block $V_i$.
To save memory, we use a packed representation with $\lceil \log({\max_{e \in E} |e|}) \rceil$ bits per entry for the $\ensuremath{\mathrm{\Phi}}(e,V_i)$-values, and we use a bitset of size $k$ to store the connectivity set $\ensuremath{\Lambda}(e)$.
Using \emph{pop-count} and \emph{count-leading-zeroes} instructions, we can efficiently iterate over the connectivity sets.
We use a separate spin-lock for each net $e$ to synchronize writes to $\ensuremath{\mathrm{\Phi}}(e,V_i)$ and $\ensuremath{\Lambda}(e)$, since we cannot use atomic fetch-and-add instructions due to the packed representation.
Each thread holds at most one spin-lock at a time, and, in particular, we do not lock all incidents nets of a vertex before moving it.
Reads are not synchronized.

\subsection{Attributed Gains.}\label{sec:attributed_gain}

Since we cannot rely on the correctness of computed gains, we additionally compute an attributed gain for each move based on the synchronized writes to $\ensuremath{\mathrm{\Phi}}(e, V_i)$.
We attribute a connectivity reduction by $\omega(e)$ to the move that reduces $\ensuremath{\mathrm{\Phi}}(e, V_i)$ to zero and an increase by $\omega(e)$ for increasing it to one.
Since we only lock one incident net at a time (not all at once) when moving a vertex, this scheme may distribute the contributions to different threads.
Hence, there is still no guarantee on the correctness of one attributed gain.
However, the sum of the attributed gains equals the overall connectivity reduction.
We use attributed gains as a secondary check for our label propagation refinement algorithm and to correctly track the connectivity metric.

\subsection{Gain Caching.}\label{sec:gain_cache}

For our FM algorithm, we propose to use a gain cache~\cite{KAHYPAR-K, FromPQs} as we do not move vertices immediately after exploring them.
We use atomic fetch-and-add instructions to update the gains as vertices are moved.
Instead of storing $g_i(u)$, we store $b(u)$ and $p_i(u)$ separately for each vertex $u$, so that changes to $b(u)$ only require one update, instead of updates to $k$ gain values.
Gains can be looked up in constant time and we use $\mathcal{O}(|V| \cdot (k+1))$ memory in total.
Now, let vertex $u$ be moved from $V_a$ to $V_b$.
For each net $e \in I(u)$, we update $b(u)$ and $p_i(u)$ using atomic fetch-and-add instructions as follows:
\begin{enumerate}
\item If $\Phi(e, V_a) = 0$, then $\forall v \in e: p_a(v) = p_a(v) + \omega(e)$
\item If $\Phi(e, V_a) = 1$, then $\forall v \in e \cap V_a: b(v) = b(v) + \omega(e)$
\item If $\Phi(e, V_b) = 1$, then $\forall v \in e: p_b(v) = p_b(v) - \omega(e)$
\item If $\Phi(e, V_b) = 2$, then $\forall v \in e \cap V_b: b(v) = b(v) - \omega(e)$
\end{enumerate}

The update conditions are checked via the synchronized writes to $\Phi(e, V_a)$ and $\Phi(e, V_b)$.
Since we use only one memory location for $b(u)$, and not one for each block, the term can no longer be correctly updated after vertex $u$ is moved.
Our FM algorithm is organized in rounds in which each vertex can be moved at most once.
Therefore, we recalculate $b(u)$ for every moved vertex $u$ after each round.

\subsection{Parallel Gain Recalculation.}\label{sec:fm:gain_recalc}

Finally, we propose a parallel algorithm to recompute exact gains of vertex moves if they are supposed
to be performed in a given order, as is the case for FM.
This approach is of independent interest to graph partitioning, as \texttt{Mt-KaHIP}~\cite{MT-KAHIP}~does this step sequentially.

Given a sequence of vertex moves $\mathcal{M} = \langle m_1, \dots, m_t \rangle$, we want to compute the exact gain of each move, as though they were performed sequentially in this order.
Let $V_i^j$ denote the vertices in block $V_i$ after the first $j-1$ moves are performed, i.e., $m_j$ is the next move to be performed.
Now, let $m_j$ move vertex $u_j$ from block $V_a$ to $V_b$.
Recall that the gain of $m_j$ is $\omega(\{ e \in I(u_j) \mid \Phi(e, V_a^j) = 1 \}) - \omega(\{ e \in I(u_j) \mid \Phi(e, V_b^j) = 0 \})$.

The following lemma yields equivalent conditions to $\Phi(e, V_a^j) = 1$ and $\Phi(e, V_b^j) = 0$ that are easier and more memory-efficient to compute in parallel than to compute all $\Phi(e, V_a^j)$ values.
The argument relies on the fact that each vertex can be moved at most once during an FM round.
We define the out-moves $\mu_{\text{out}}(e, V_i)$ of $V_i$ and $e \in E$ as the move indices $j$ such that $u_j \in e$ and $m_j$ moves $u_j$ out of $V_i$, i.e., those moves for which a pin of $e$ is moved out of $V_i$.
Analogously, we define the in-moves $\mu_{\text{in}}(e, V_i)$ such that $m_j$ moves $u_j$ into $V_i$.
Further, we define $\Psi(e, V_i) := \Phi(e, V_i^1) - |\mu_{\text{out}}(e, V_i)|$ as the number of pins of $e$ initially in $V_i$ that were removed from $V_i$ over the course of the FM round.
For simpler notation, we use $\max(\emptyset) = 0$ and $\min(\emptyset) = \infty$.

\begin{lemma}\label{lemma:gain_equivalence}
	Let $j \in \{1, \dots, t\}$, let $m_j$ move $u_j$ from $V_a$ to $V_b$, and let $e \in I(u)$.

	Then $\Phi(e, V_a^j) = 1$ if and only if ${\Psi(e, V_a) = 0}$, ${j = \max(\mu_{\text{out}}(e, V_a))}$, and ${\min(\mu_{\text{in}}(e, V_a)) > j}$.

	Similarly, $\Phi(e, V_b^j) = 0$ if and only if $\Psi(e, V_b) = 0$, $j = \min(\mu_{\text{in}}(e, V_b))$, and $\max(\mu_{\text{out}}(e, V_b)) < j$.
\end{lemma}
\begin{proof}
	We only prove the first statement, the second can be proven similarly.
	"$\Rightarrow$":
	If $\Phi(e, V_a^j) = 1$ then $u_j$ is the last vertex of $V_a^1$ remaining, as no vertex moved into $V_a$ this round can be moved out again.
	Hence, it follows that $j = \max(\mu_{\text{out}}(e, V_a))$ and thus also $\Phi(e, V_a^1) = |\mu_{\text{out}}(e, V_a)|$.
	Now, we prove $l := \min(\mu_{\text{in}}(e, V_a)) > j$.
	First, observe that $l \neq j$ since $m_j$ moves out of $V_a$.
	Assume for the sake of contradiction that $l < j$.
	Then $\{u_l, u_j\} \subset V_a^j$ and thus $\Phi(e, V_a^j) \geq 2$, a contradiction to $\Phi(e, V_a^j) = 1$.

	"$\Leftarrow$ ":
	$\Psi(e, V_a) = 0$ means that all vertices of $V_a^1$ were moved out of $V_a$ in the current FM round.
	If $j=\max(\mu_{\text{out}}(e, V_a))$ then $m_j$ is the last of these moves.
	Additionally, $j < \min(\mu_{\text{in}}(e, V_a))$ means that no vertex was moved into $V_a$ prior to $m_j$.
  Combining these yields $\Phi(e, V_a^{j+1}) = 0$, from which $\Phi(e, V_a^j) = 1$ follows, because $m_j$ moves out of $V_a$.

\end{proof}

We iterate over $\mathcal{M}$ in parallel, and over the incident nets $e \in I(u_j)$ sequentially.
In each step, we use early-exit compare-and-swap loops to update $\max(\mu_{\text{out}}(e, V_a))$ and $\min(\mu_{\text{in}}(e, V_b))$, and atomic fetch-and-add instructions for $\Psi(e, V_a)$.
In a second step, we again iterate over $\mathcal{M}$ in parallel and use the data from the first step to assign the exact gain to each move using Lemma~\ref{lemma:gain_equivalence}.

The compare-and-swap loops require $O(|E| \cdot k)$ memory.
For nets $e$ with only few pins, it is feasible to recompute the data from Lemma~\ref{lemma:gain_equivalence} at every moved pin.
Currently, our implementation does the recomputation if $|e|=2$, thus saving $O(k)$ memory on every such edge.
This is sufficient to make the memory overhead negligible on our benchmark sets.

\section{Label Propagation}\label{sec:label-propagation}
Our first refinement algorithm is a parallel version of the greedy refinement heuristic implemented in \texttt{hMetis-K}~\cite{HMETIS-K}, which is
also called \emph{size-constrained label propagation} in \texttt{ParHIP}~\cite{PARHIP}.
It bears resemblance to the clustering algorithms for coarsening and community detection.
In each round, we iterate in parallel over all boundary vertices that are \emph{eligible} to be moved.
In the first round, each boundary vertex is eligible.
For each eligible vertex $u$ we compute the gain of moving it to any of its neighboring blocks by iterating over its incident nets $e \in \incnets(u)$ and their connectivity sets $\Lambda(e)$.
Then, we move $u$ to the block with the highest positive gain that does not violate the balance constraint.
We also perform moves with zero gain that improve the balance.
After the move, we attribute a gain to the move based on the partition data structure updates, as described in Section~\ref{sec:attributed_gain}.
If the attributed gain is negative, we revert the move.
We rarely observed this in practice.
If $u$ is moved, then $u$ and its neighbors are made eligible to move in the next round.
Experiments indicate that a small number of rounds (we use $5$) suffice for convergence~\cite{HMETIS-K}.
We use atomic fetch-and-add instruction to update block weights to ensure that the balance constraint is never violated.

\section{Direct $k$-way FM}\label{sec:fm}
Our second refinement algorithm is a parallel version of the classical FM local search~\cite{FM}.
Sequential FM consists of two phases: \emph{finding a sequence of moves} by repeatedly performing a feasible move with highest gain followed by \emph{reverting moves back to the prefix with the highest gain} in that sequence.
We implement a relaxed version of the first phase that performs non-overlapping \emph{localized} FM searches on different threads to obtain a global sequence of moves.
The second phase consists of two steps: recalculate the exact gain of each move in that sequence (for which we propose a novel parallel algorithm in Section~\ref{sec:fm:gain_recalc}), followed by a combined parallel prefix sum and reduce operation to find the prefix in that sequence that provides the best gain and is balanced.
In the following, we describe the first phase in more detail.

\subsection{Localized Searches.}
An FM \emph{round} starts with inserting all boundary vertices into a globally shared task queue and randomly shuffling the queue.
We perform independent \emph{localized} FM local searches to find promising vertex moves.
Each search gradually expands around a constant number (we use 25) of starting vertices polled from the task queue.
The searches are non-overlapping, i.e., threads acquire exclusive ownership of vertices, although hyperedges can touch multiple searches.
Inserting a vertex $u$ into the local search of a thread entails acquiring ownership of $u$ by atomically setting a bit, looking up the gains for moving $u$ to any of the blocks, and inserting $u$ into a priority queue (PQ) with the highest gain as key.
Gains are stored and updated using a gain cache as explained in Section~\ref{sec:gain_cache}, that is shared among threads.
In particular, gain cache updates are visible to other threads, which yields adequately accurate gains at the time a vertex is moved.

We repeatedly extract and perform the feasible move with highest gain in the PQ.
After extracting a vertex from the PQ, we recompute the best move for that vertex using the gain cache.
If the gain of this move is worse than the key stored in the PQ, we reinsert the vertex with its new gain.
This way, we update the PQs to changes made by other threads.
After moving a vertex, we insert its neighbors into the local search or update their gain in the PQ if they were already inserted.
We skip vertices that were already moved or are owned by other threads.
The localized search finishes if the PQ becomes empty, the adaptive stopping rule of \texttt{KaHyPar}~\cite{KAHYPAR-K, ADAPTIVE-STOP-RULE} is triggered, or more than a certain number of threads unsuccessfully polled the task queue.
The last condition ensures a certain level of parallelism.
After each localized search, we release ownership of vertices that were not moved so that other threads can use them.
If in the meantime another thread polled a released vertex from the task queue, we reinsert it.
We repeatedly start localized searches until the task queue is empty.
Once the task queue is empty, we proceed to the second phase, where we recalculate the gains of the global move sequence (see Section~\ref{sec:fm:gain_recalc}) and keep the highest gain prefix of the global move sequence.

\subsection{Applying Moves.}
After each localized search, we keep the moves in the best prefix of the thread-local move sequence, and revert the remaining moves.
We use fetch-and-add instructions to assign global IDs to vertex moves as they are applied to the global partition, and store them in a vector that represents the global move sequence.
We use two different ways to apply moves to the global partition.
In the \emph{global} approach, moves are immediately applied as the searches find them.
This means moves are also reverted on the global partition and other threads temporarily see these.
In the \emph{local} approach, moves are first applied to a thread-local partition and only the best local prefix is applied to the global partition.
This requires thread-local hash tables for storing changes to the partition and gains.
The local approach yields better solution quality, but can incur a large memory and running time overhead on instances with many large nets, e.g., dual SAT instances~\cite{SAT14}.
By default we use \emph{local}.
After each localized search we check if the memory consumption of the hash tables exceeds a threshold.
If the threshold is exceeded, we switch to \emph{global}.
After each FM round we check if a time limit depending on the coarsening time is exceeded.
If so, we switch to \emph{global} and stop releasing vertices at the end of localized searches.

\section{Rebalancing}\label{sec:rebalancing}
While our refinement algorithms are guaranteed to produce balanced solutions, it turns out that intermediate balance violations improve solution quality.
The intuition behind this is that localized FM searches may each find good improvements but their combination is barely infeasible.
Hence, we relax the balance constraint for the second FM phase (the rollback step) by using $\varepsilon' = 1.25 \cdot \varepsilon$ instead of $\varepsilon$.
This value was obtained from preliminary experiments.
If the partition is still imbalanced on the finest level, we rebalance it using an approach that is similar to label propagation.
We iterate over the vertices in parallel.
If a vertex is in an overloaded block and can be moved with non-negative gain, we perform the move immediately.
Negative-gain moves are collected in thread-local priority queues.
If the partition is still imbalanced after performing all non-negative gain moves, we perform the moves with the smallest increase in connectivity from the priority queues, in a second step.

\subsection{Instances.}

Our instances are derived from four sources encompassing three application domains: the ISPD98 VLSI Circuit Benchmark Suite~\cite{ISPD98}, the DAC 2012 Routability-Driven Placement Contest~\cite{DAC}, the SuiteSparse Matrix Collection~\cite{SPM}, and the 2014 SAT Competition~\cite{SAT14}.
We translate sparse matrices to hypergraphs using the row-net model~\cite{PATOH} and SAT instances to three different hypergraph representations: \emph{literal}, \emph{primal}, and \emph{dual}~\cite{MANN-PAPA14, PAPA-MARKOV} (for more details see also~\cite{KAHYPAR-CA}).
All hypergraphs have unit vertex and net weights.

For comparison with sequential partitioners, we use the established benchmark set of Heuer and Schlag~\cite{KAHYPAR-CA}, which contains $488$ hypergraphs (referred to as set A).
Since set A contains many small instances, we composed a new benchmark set (referred to as set B) consisting of $94$ much larger hypergraphs to evaluate speedups and to compare \texttt{Mt-KaHyPar}~with parallel partitioners.
It consists of $42$ instances from the SuiteSparse Matrix Collection~\cite{SPM} that represents a randomly sampled subset of all available matrices with more than
$15$ million non-zero entries, all ten~\texttt{DAC} instances \cite{DAC} of set A, as well as the $24$ largest SAT instances of set A extended with
$18$ additional larger instances from~\cite{SAT14}.
\footnote{The benchmark sets and detailed statistics of their properties are publicly available from \url{http://algo2.iti.kit.edu/heuer/alenex21/}.}

\subsection{System.}

We use two different machines.
Machines of type A are nodes of a cluster with Intel Xeon Gold 6230 processors ($2$ sockets with $20$ cores each) running at $2.1$ GHz with $96$GB RAM.
These are used for the comparison with sequential partitioners, as these experiments take roughly 3.5 CPU years overall.
Machine B is an AMD EPYC Rome 7702P ($1$ socket with $64$ cores) running at $2.0$--$3.35$ GHz with $1024$GB RAM.

On set A and machine A, we compare \texttt{Mt-KaHyPar}~to the following sequential hypergraph partitioners: \texttt{KaHyPar-CA}~\cite{KAHYPAR-CA}~($n$-level partitioner with similiar algorithmic components as \texttt{Mt-KaHyPar}), the latest version \texttt{KaHyPar-HFC}~\cite{KAHYPAR-HFC} (extends \texttt{KaHyPar-CA} with flow-based refinement), the recursive bisection version (\texttt{hMetis-R}) of \texttt{hMetis}~$2.0$~\cite{HMETIS}, as well as the speed (\texttt{PaToH-S}), default (\texttt{PaToH-D}), and quality preset (\texttt{PaToH-Q}) of \texttt{PaToH} $3.3$~\cite{PATOH}.

On set B and machine B, we compare \texttt{Mt-KaHyPar}~to the distributed partitioner \texttt{Zoltan} $3.83$~\cite{ZOLTAN}.
Unfortunately, we are not able to include \texttt{Parkway}~\cite{PARKWAY-2}.
The \texttt{Parkway} version available on GitHub\footnote{\url{https://github.com/parkway-partitioner/parkway}} either hangs infinitely or crashes with a segmentation fault.
Additionally, we asked the author of \texttt{PaToH} for a version with parallel coarsening~\cite{PARALLEL-PATOH} but were unable to obtain it.
Since only one phase is parallel, even the good speedups of factor 5-6 on 8 cores in that phase do not translate to overall speedups greater than a factor of 2.

\subsection{Methodology.}

Experiments on set A are executed with $k \in \{2,4,8,16,32,64,128\}$, $\varepsilon = 0.03$, ten different seeds and a time limit of eight hours.
Experiments on set B are executed with $k \in \{2,8,16,64\}$, $\varepsilon = 0.03$, five seeds and a time limit of two hours.
Each partitioner optimizes the connectivity metric which we also refer to as the quality of a partition.

For each instance (hypergraph and number of blocks $k$), we aggregate quality and running times using the arithmetic
mean (over all seeds).
To further aggregate over multiple instances, we use the harmonic mean for relative speedups, and the geometric mean for absolute running times, to give each instance a comparable influence.
Runs with imbalanced partitions are not excluded from aggregated running times.
For runs that exceeded the time limit we use the time limit in the aggregates.
Only if all runs of an algorithm produced imbalanced partitions on an instance, we mark it with \ding{55} in the plots, and similarly mark
instances for which all runs exceeded the time limit with \ClockLogo.

To compare the solution quality of different algorithms, we use \emph{performance profiles}~\cite{PERFORMANCE-PROFILES}.
Let $\mathcal{A}$ be the set of all algorithms we want to compare, $\mathcal{I}$ the set of instances, and $q_{A}(I)$ the quality of algorithm
$A \in \mathcal{A}$ on instance $I \in \mathcal{I}$.
For each algorithm $A$, we plot the fraction of instances ($y$-axis) for which $q_A(I) \leq \tau \cdot \min_{A' \in \mathcal{A}}q_{A'}(I)$, where $\tau$ is on the $x$-axis.
For $\tau = 1$, the $y$-value indicates the percentage of instances for which an algorithm $A \in \mathcal{A}$ performs best.
Note that these plots relate the quality of an algorithm to the best solution and thus do not permit a full ranking of three or more algorithms.

Additionally, we use the \emph{effectiveness tests} proposed by Ahkremtsev et. al.~\cite{MT-KAHIP} to compare solution quality when two algorithms are given a similar running time, by performing virtual repetitions with the faster algorithm.
We generate virtual instances that we compare using performance profiles.
Consider two algorithms $A$ and $B$, and an instance $I$.
We first sample one run of both algorithms on $I$.
Let $t_A^1, t_B^1$ be their running times and assume that $t_A^1 \geq t_B^1$.
We sample additional runs without replacement for $B$ until their accumulated time exceeds $t_A^1$ or all runs have been sampled.
Let $t_B^2, \dots, t_B^l$ denote their running times.
We accept the last run with probability $(t_A^1 - \sum_{i = 1}^{l-1} t_B^i) / t_B^l$ so that the expected time for the sampled runs of $B$ equals $t_A^1$.
The solution quality is the minimum out of the sampled runs.
For each instance, we generate $20$ virtual instances.

\subsection{Scalability.}

\DTLloaddb[noheader, keys={key,value}]{speedup}{experiments/speedup/speedup.dat}

\begin{table
  \footnotesize
  \captionsetup{font=footnotesize}
  \centering
  \caption{Harmonic mean speedups over all instances and instances with a single-threaded running time $\ge 100$s for
           the total partition time (T), community detection (CD), coarsening (C), initial partitioning (IP), label propagation (LP) and FM.}
  \label{tbl:hmean_speed_ups}
  \begin{tabular}{lr|rrrrrr}
  \multicolumn{2}{r|}{Num. Threads} & T & CD & C & IP & LP & FM \\
  \midrule
  \multirow{3}{*}{All}        & $4$ &  $\placeholder{speedup}{speedUpTotalTimeP4S0}$   & $\placeholder{speedup}{speedUpCommunityDetectionP4S0}$   &
                                           $\placeholder{speedup}{speedUpCoarseningP4S0}$  & $\placeholder{speedup}{speedUpInitialPartitioningP4S0}$ &
                                           $\placeholder{speedup}{speedUpLabelPropagationP4S0}$ & $\placeholder{speedup}{speedUpFMP4S0}$ \\
                              & $16$ & $\placeholder{speedup}{speedUpTotalTimeP16S0}$   & $\placeholder{speedup}{speedUpCommunityDetectionP16S0}$   &
                                           $\placeholder{speedup}{speedUpCoarseningP16S0}$  & $\placeholder{speedup}{speedUpInitialPartitioningP16S0}$ &
                                           $\placeholder{speedup}{speedUpLabelPropagationP16S0}$ & $\placeholder{speedup}{speedUpFMP16S0}$ \\
                              & $64$ & $\placeholder{speedup}{speedUpTotalTimeP64S0}$   & $\placeholder{speedup}{speedUpCommunityDetectionP64S0}$  &
                                           $\placeholder{speedup}{speedUpCoarseningP64S0}$  & $\placeholder{speedup}{speedUpInitialPartitioningP64S0}$ &
                                           $\placeholder{speedup}{speedUpLabelPropagationP64S0}$ & $\placeholder{speedup}{speedUpFMP64S0}$ \\
  \multirow{3}{*}{$\ge 100$s} & $4$  & $\placeholder{speedup}{speedUpTotalTimeP4S100}$ & $\placeholder{speedup}{speedUpCommunityDetectionP4S100}$ &
                                           $\placeholder{speedup}{speedUpCoarseningP4S100}$ & $\placeholder{speedup}{speedUpInitialPartitioningP4S100}$ &
                                           $\placeholder{speedup}{speedUpLabelPropagationP4S100}$ & $\placeholder{speedup}{speedUpFMP4S100}$ \\
                              & $16$ & $\placeholder{speedup}{speedUpTotalTimeP16S100}$ & $\placeholder{speedup}{speedUpCommunityDetectionP16S100}$ &
                                           $\placeholder{speedup}{speedUpCoarseningP16S100}$ & $\placeholder{speedup}{speedUpInitialPartitioningP16S100}$ &
                                           $\placeholder{speedup}{speedUpLabelPropagationP16S100}$ & $\placeholder{speedup}{speedUpFMP16S100}$ \\
                              & $64$ & $\placeholder{speedup}{speedUpTotalTimeP64S100}$ & $\placeholder{speedup}{speedUpCommunityDetectionP64S100}$ &
                                           $\placeholder{speedup}{speedUpCoarseningP64S100}$ & $\placeholder{speedup}{speedUpInitialPartitioningP64S100}$ &
                                           $\placeholder{speedup}{speedUpLabelPropagationP64S100}$ & $\placeholder{speedup}{speedUpFMP64S100}$ \\
  \midrule
  \multicolumn{2}{r|}{\footnotesize{Inst. $\ge 100$s $[\%]$}} & $\placeholder{speedup}{percentageInstancesGreaterTotalTimeS100}$ & $\placeholder{speedup}{percentageInstancesGreaterCommunityDetectionS100}$ &
                                                     $\placeholder{speedup}{percentageInstancesGreaterCoarseningS100}$ & $\placeholder{speedup}{percentageInstancesGreaterInitialPartitioningS100}$ &
                                                     $\placeholder{speedup}{percentageInstancesGreaterLabelPropagationS100}$ & $\placeholder{speedup}{percentageInstancesGreaterFMS100}$ \\
  \end{tabular}
\vspace*{-0.6cm}
\end{table}

\begin{figure*
  \vspace*{-2cm}
  \centering
  \externalizedfigure{0}{experiments/speedup/speedup.tex} %
  \vspace*{-2.5cm}
  \caption{Arithmetic mean speedup per instance (points) and cumulative harmonic mean speedup (lines) of \texttt{Mt-KaHyPar}~with $p \in \{4,16,64\}$ for each algorithmic component on set B. }
  \label{fig:speedup}
\end{figure*}

\begin{figure*
  \centering
  \begin{minipage}{.3\textwidth}
    \hspace{-0.75cm}
    \externalizedfigure{1}{experiments/kahypar_benchmark_set/kahypar_quality_patoh.tex} %
    \vspace{-0.5cm}
  \end{minipage} %
  \begin{minipage}{.3\textwidth}
    \externalizedfigure{2}{experiments/kahypar_benchmark_set/kahypar_quality_high_quality.tex} %
    \vspace{-0.5cm}
  \end{minipage} %
  \begin{minipage}{.3\textwidth}
    \hspace{0.25cm}
    \externalizedfigure{3}{experiments/big_benchmark_set/big_quality.tex} %
    \vspace{-0.5cm}
  \end{minipage} %
  \caption{Performance profiles comparing the solution quality of \texttt{Mt-KaHyPar}~with \texttt{PaToH} (left),
           \texttt{hMetis} and \texttt{KaHyPar} (middle) on set A, as well as \texttt{Zoltan} and \texttt{PaToH} (right) on set B.}
  \label{fig:quality}
  \vspace{-0.25cm}
\end{figure*}

\begin{figure*}
  \hspace{0.65cm}
	\begin{minipage}{.3\textwidth}
		\vspace{0.185cm}
		\hspace{-0.75cm}
		\externalizedfigure{4}{experiments/kahypar_benchmark_set/mt_kahypar_vs_hmetis_r.tex} %
		\vspace{-0.5cm}
	\end{minipage} %
	\begin{minipage}{.3\textwidth}
		\vspace{0.185cm}
		\externalizedfigure{5}{experiments/kahypar_benchmark_set/mt_kahypar_vs_kahypar_ca.tex} %
		\vspace{-0.5cm}
	\end{minipage} %
	\begin{minipage}{.3\textwidth}
		\hspace{0.25cm}
		\vspace{-0.185cm}
		\externalizedfigure{6}{experiments/kahypar_benchmark_set/mt_kahypar_vs_kahypar_hfc.tex} %
		\vspace{-0.5cm}
	\end{minipage} %
\caption{Effectiveness tests comparing \ExpAlgo{Mt-KaHyPar}{10} with \texttt{hMetis-R}, \texttt{KaHyPar-CA} and \texttt{KaHypar-HFC} on set A.
         The faster algorithm performs (up to 10) repetitions so that both algorithms invest similar amounts of time.}
\label{fig:effectiveness_tests_quality}
\end{figure*}

\begin{figure*}[!ht]
  \centering
  \begin{minipage}{.49\textwidth}
    \externalizedfigure{7}{experiments/kahypar_benchmark_set/kahypar_relative_runtime.tex} %
    \vspace{-0.25cm}
  \end{minipage} %
  \begin{minipage}{.49\textwidth}
    \externalizedfigure{8}{experiments/big_benchmark_set/big_relative_runtime.tex} %
    \vspace{-0.25cm}
  \end{minipage} %
  \caption{Running times of different sequential resp. parallel partitioners relative
           to \ExpAlgo{Mt-KaHyPar}{10} on set A (left) resp. \ExpAlgo{Mt-KaHyPar}{64} on set B (right).}
  \label{fig:running_time}
  \vspace{-0.25cm}
\end{figure*}

In Figure~\ref{fig:speedup} and Table~\ref{tbl:hmean_speed_ups}, we summarize the speedups of \texttt{Mt-KaHyPar}~with varying number of threads ($p \in \{4,16,64\}$) for each algorithmic component on set B.
In the plot, we represent the speedup of each instance as a point and the cumulative harmonic mean speedup over
all instances with a single-threaded running time $\ge x$ seconds with a line.

The overall harmonic mean speedup of \texttt{Mt-KaHyPar}~is $\placeholder{speedup}{speedUpTotalTimeP4S0}$ for $p = 4$,
$\placeholder{speedup}{speedUpTotalTimeP16S0}$ for $p = 16$ and $\placeholder{speedup}{speedUpTotalTimeP64S0}$ for $p = 64$.
If we only consider instances with a single-threaded running time $\ge 100$s, we achieve a harmonic mean speedup
of $\placeholder{speedup}{speedUpTotalTimeP64S100}$ for $p = 64$.
For $p = 4$, the speedup is at least $\placeholder{speedup}{minSpeedUpOfBest90PercentP4}$ on over $90\%$ of our instances.

Community detection and coarsening share many similarities in their implementation and both show reliable speedups for increasing number of threads.
For the remaining three components, we observe that longer single-threaded execution leads to substantially better speedups.
For initial partitioning, increasing the number of threads from $16$ to $64$ can even be harmful for instances with a single-threaded running time of one second or less.
While label propagation refinement yields the least promising speedups, it is substantially faster than the other components, taking less than 10\% of the overall running time on over 95\% of the instances, for $p=64$.
Our algorithms do not perform any expensive arithmetic calculations.
Hence, scalability is limited by memory bandwidth, which makes achieving perfect speedups difficult.

\subsection{Comparison with other Systems.}

\DTLloaddb[noheader, keys={key,value}]{sequential}{experiments/kahypar_benchmark_set/sequential.dat}
\DTLloaddb[noheader, keys={key,value}]{parallel}{experiments/big_benchmark_set/parallel.dat}
Figure~\ref{fig:quality} compares the quality of \texttt{Mt-KaHyPar}~with different sequential (left and middle) and parallel hypergraph partitioners (right).
If we compare \ExpAlgo{Mt-KaHyPar}{10} with each sequential partitioner individually, \ExpAlgo{Mt-KaHyPar}{10} produces partitions with better quality than
\texttt{PaToH-S}, \texttt{PaToH-D}, \texttt{PaToH-Q}, \texttt{hMetis-R}, \texttt{KaHyPar-CA}, \texttt{KaHyPar-HFC} on
$\placeholder{sequential}{mtKaHyParvsPaToHSMtKaHyPar10Tau100}\%$, $\placeholder{sequential}{mtKaHyParvsPaToHDMtKaHyPar10Tau100}\%$,
$\placeholder{sequential}{mtKaHyParvsPaToHQMtKaHyPar10Tau100}\%$, $\placeholder{sequential}{mtKaHyParvshMetisRMtKaHyPar10Tau100}\%$,
$\placeholder{sequential}{mtKaHyParvsKaHyParCAMtKaHyPar10Tau100}\%$, and $\placeholder{sequential}{mtKaHyParvsKaHyParHFCMtKaHyPar10Tau100}\%$
of the instances of set A, respectively.
For set A, we use 10 cores with \texttt{Mt-KaHyPar}~as this is a typical number of available cores in current commodity workstations.
On set B, \ExpAlgo{Mt-KaHyPar}{64} computes better partitions than \ExpAlgo{Zoltan}{64} on $\placeholder{parallel}{mtKaHyParvsZoltanMtKaHyParTau100}\%$ of the instances. Further, the quality of at least $\placeholder{parallel}{mtKaHyParvsZoltanZoltanTauInv110}\%$ of the partitions produced by \ExpAlgo{Zoltan}{64} are more than $10\%$ worse than those of \ExpAlgo{Mt-KaHyPar}{64}.

In the effectiveness tests presented in Figure~\ref{fig:effectiveness_tests_quality}, where algorithms receive similar running times via virtual repetitions, \ExpAlgo{Mt-KaHyPar}{10} finds better solutions than \texttt{hMetis-R} and similar quality solutions as \texttt{KaHyPar-CA}.
However, the more advanced approaches of \texttt{KaHyPar-HFC} cannot be compensated by additional repetitions of \texttt{Mt-KaHyPar}.
Effectiveness tests with the other algorithms can be found in Figure~\ref{fig:appendix:effectiveness} in Appendix~\ref{sec:appendix:effectiveness}.

Figure~\ref{fig:running_time} shows running times of each partitioner relative to \texttt{Mt-KaHyPar}.
We additionally report absolute running times as well as their geometric mean in Figure~\ref{fig:appendix:absolute_times} in Appendix~\ref{sec:appendix:absolute_times}.
On set A, \ExpAlgo{Mt-KaHyPar}{10} is consistently faster than \texttt{hMetis}, \texttt{KaHyPar} and \texttt{PaToH-Q}.
\texttt{PaToH-D} is faster on 60\% of the instances, and \texttt{PaToH-S} on 72\%, however, this is due to the small instances.
The geometric mean times of \texttt{PaToH-D} and \ExpAlgo{Mt-KaHyPar}{10} are similar at 1.17s vs 1.5s.
On the larger instances of set B, \ExpAlgo{Mt-KaHyPar}{4} is slightly faster \texttt{PaToH-D} while providing better solutions on 83\% of the instances, and being able to scalably utilize larger numbers of threads.
As shown in Figure~\ref{fig:appendix:graph_partitioning_and_thread_dependent_quality} (right) of Appendix~\ref{sec:appendix:graph_partitioning_and_thread_dependent_quality}, increasing the number of threads does not adversely affect solution quality of \texttt{Mt-KaHyPar}.
\ExpAlgo{Mt-KaHyPar}{64} dominates \ExpAlgo{Zoltan}{64} since it is 2.1 times faster in the geometric mean while achieving much better quality -- see Figure~\ref{fig:quality}.

Figure~\ref{fig:appendix:graph_partitioning_and_thread_dependent_quality} (left) in Appendix~\ref{sec:appendix:graph_partitioning_and_thread_dependent_quality} provides an additional comparison with parallel graph partitioners.
We see that \texttt{Mt-KaHyPar} achieves similar quality as \texttt{Mt-KaHiP} while only incurring a slowdown by a factor of $2$ in the geometric mean.
The slowdown is expected since we use substantially more complicated data structures.

redpajama_set_name: RedPajamaArXiv


Olivia Bloch-Lainé was born in 1972. She graduated from the Ecole Nationale Supérieure des Arts Visuels de la Cambre in Brussels. She lives and works in Paris.
Unfortunately, there are currently no available works by Olivia Bloch-Lainé.
Olivia Bloch-Lainé doesn't have any exhibitions.
Follow Olivia Bloch-Lainé to receive a notification as soon as new exhibitions are added.


text:
Pass the salt -- Using the fly to understand how pregnancy drives food cravings
Complete the form below and we will email you a PDF version of "Pass the salt -- Using the fly to understand how pregnancy drives food cravings "
Pregnancy is famed to inspire relentless food cravings in women, who will allegedly stop at nothing until they get the food they desire, be it a grilled cheese sandwich, olives, or ice-cream on a cold winter night. It is commonly believed that these cravings are not just arbitrary whims, but are linked, at least to some extent, to the nutritional needs of the fetus their bodies are nurturing. This is particularly true for nutrients such as proteins and salt.
What changes in the brain during pregnancy cause food cravings? More specifically, how does the brain know what the body needs and then, what changes in the brain's perception of the world lead women to seek out certain foods during pregnancy?
To pursue the answers to these challenging questions, the team of Carlos Ribeiro at the Champalimaud Centre for the Unknown in Lisbon, chose to study the neural basis of changes in nutrient intake in female fruit flies after mating.
"Nutrition is a highly complex topic. To understand how the brain regulates nutrient intake, you need to work in an organism that gives you access to a lot of diverse technologies. In that respect, the fruit fly is unbeatable," says Dr. Ribeiro. "We wanted to exploit these tools to uncover how the female fly's food preferences changed after mating. Many mammalian species increase their preference for salt during pregnancy; but until now it was not known if the fruit fly shared this behaviour."
Following a series of experiments, the researchers revealed, for the first time, not only that flies indeed share mammals' inclination towards salt during pregnancy, but also that higher salt levels in the diet result in higher production of offspring.
"We found that there is a direct correlation between the amount of salt in the diet and the amount of eggs they were able to produce," explains Dr. Ribeiro. "It seems that salt is important everywhere, from flies, to elephants, to humans. It also suggests the existence of unifying biological principles underlying this behavior that could be traced across species."
Surprisingly, even though different levels of salt directly influenced offspring production, the researchers discovered that the salt craving was not based on the precise needs of the body. On the contrary, "even if their egg production was disabled, mated females showed increased salt preference, demonstrating that salt-craving was independent of the actual needs of the body," says Dr. Ribeiro.
It appears that the brain of the female knows that she will need more salt to produce eggs and so it automatically changes the way the animal perceives salt to allow the animal to ingest higher amounts of this important nutrient. Just as in humans, the "tongue" of the flies becomes much more responsive to the taste of salt, leading her to prefer saltier food. The key question now was: "What is the biological mechanism that leads to this change in salt sensation in pregnant animals?"
According to Samuel Walker, the PhD student in the Ribeiro lab who was the main researcher of this study, during mating the male injects a molecule called Sex Peptide into the female which manipulates the taste perception of the female. "The molecule activates neurons in the uterus of the female. From there, we found that a short chain of neuronal interactions signals the brain to ´dial up the salt preference.'"
By piecing together this complicated puzzle, the researchers were able to demonstrate that salt-craving exists in flies much as it does in mammals, and that this craving plays an important role in their reproductive abilities. They were also able to identify the trigger for salt-craving and map several steps in the neural circuitry that brings about this behavioral change. "Now", concludes Dr. Ribeiro, "we move on to the next question, which is to identify how the brain's response to salt changes after mating to bring about this cross-species behavior. We will continue using the fruit fly, an organism that is unbeatable in its array of genetic tools, which will be essential to understand a topic as complex as nutrition."
JLM&A, SA
Walker SJ, Corrales-Carvajal VM, Ribeiro C. Postmating Circuitry Modulates Salt Taste Processing to Increase Reproductive Output in Drosophila. Current Biology, Published Online September 24 2015. doi: 10.1016/j.cub.2015.08.043

redpajama_set_name: RedPajamaCommonCrawl


text:
Honeymoon Romance in France: Paris & the French Riviera - 9 Days
Head to France for nine magical days in the city of love—the perfect place for a honeymoon. Paris practically begs you to plan a romantic getaway, which is exactly what you'll do, from art viewing in the Louvre to day trips to storybook chateaus. Make sure to stop by the historic city of Avignon before wiling away the time on the sunny white-sand beaches of the south.
Explore Roman ruins in Avignon
Spend time in Cannes and Monaco
Wonder at the splendor of the Versailles estate
Tour the fairytale Châteaus de Chambord & Chenonceau
Experience the magic of Paris at night
Day 1 Welcome to France! Arrive in Paris & Evening Eiffel Tower Tour Paris
Day 2 Pastry Tour of Le Marais & Afternoon at the Louvre Paris
Day 3 Day Trip to Versailles Paris
Day 4 Day Trip to Châteaus de Chambord & Chenonceau Paris
Day 5 Train from Paris to Avignon & Afternoon in the City Avignon
Day 6 Hilltop Villages & Wine in the Luberon: Full Day Tour Avignon
Day 7 Avignon to Nice, Tour of Aix-en-Provence en Route Nice
Day 8 Private Tour of Monaco, Monte Carlo, & Eze Nice
Day 9 Au revoir, France!
Day 1: Welcome to France! Arrive in Paris & Evening Eiffel Tower Tour
Welcome to Paris!
Welcome to Paris, the City of Lights! This elegant capital boasts centuries of history, art, fashion and, of course, romance. Upon arrival, you'll be picked up from the airport and transferred to your hotel by private car. Take some time to settle in and relax before heading out to explore the streets near your accommodation before dinner.
Paris is alive and thriving with activity, day and night. It's the perfect city to indulge in a little shopping, with department stores like Lafayette and Printemps housing some of the best local designers around, and small boutique shops offering unique high-quality wares.
Colorful boulevards and historic monuments invite visitors to stroll through the downtown, while narrow alleys and cozy cafes create a romantic atmosphere. For art lovers, spending time at Paris' smaller museums is a once-in-a-lifetime experience, as the city has one of the most impressive art collections in the world. Alternatively, lazing around in the parks or at a sidewalk cafe on a sunny day is simply blissful.
After settling into your hotel, head out for your first look at the city. Spend some time walking around downtown and enjoying the sights. In the evening, meet with your private guide for a 3.5-hour exploration of the Trocadero Esplanade and Eiffel Tower. Start at the Trocadero to see its statues, monuments, and city views. Continue to the Iron Lady herself with skip-the-line tickets, giving you the most time to visit both floors and take in the incredible views from the top.
Day 2: Pastry Tour of Le Marais & Afternoon at the Louvre
Eating pastries and enjoying art is synonymous with French culture, and you'll get to do plenty of both today. Start your day with a tour of the Le Marais neighborhood with a hyper-local guide (a neighborhood resident, in fact!) to explore the secret cafes and taste the best baked goods in the city. Spend two hours sampling crépes, crème brûlée, pain au chocolat, espresso, chocolates, macarons, and more.
Visit the city's oldest food market, the Marché des Enfants Rouges, and try your hand at haggling for your favorite treat. As you walk, learn about world-famous pastry chefs: Poîlane, Jean-Paul Hévin, Jacques Genin, Pierre Hermé, and others.
In the afternoon, it's time to explore the Louvre, the world's largest art museum. Skip the lines and head right to the classics, as well as your personal favorites. Get up close to Venus de Milo and the Mona Lisa, then get some fresh air at the Tuileries Garden. In the evening, explore the Champs Elysees and the majestic Arc de Triomphe.
Day 3: Day Trip to Versailles
Walk through the Hall of Mirrors in Versailles
In the morning, head outside of the big city to the resplendent Versaille Estate. Take the train there, then head directly inside with your skip-the-line access to spend a few hours exploring the palace and grounds. Travel back in time to past centuries as you discover what life was like living in the splendor of the court of the kings and queens of France. Your historian guide will walk you from hall to gilded hall, pointing out ornately painted ceilings, the Hall of Mirrors, and the private royal quarters.
After touring the castle head outside to the manicured gardens and lawns, where a dazzling display of flowers and exotic plants delight visitors of all ages.
Enjoy lunch near the castle, then take the train back to Paris for a free afternoon in the city. Shop, enjoy the sunshine in one of the city's parks, or explore one of the city's many art museums.
Day 4: Day Trip to Châteaus de Chambord & Chenonceau
Chenonceau castle and grounds
Start the morning with a private hotel pickup for your full-day tour.
Your first stop is Chambord, whose French-Renaissance construction dates back to the early 16th century. This extravagant chateau is one of France's most famous and recognizable, thanks to its stately facade and sprawling grounds.
Take the grand double spiral staircase to the second floor to see the royal apartments of François I and Louis XIV. During its heyday, the chateau and nearby forests were used for royal hunts and other pleasure activities. Continue up to the terraces, where views of the surrounding landscape offer a glimpse into the charmed lives of the castle's royals. From here you can also get a good look at the roofing and chimneys of the chateau, which rises magnificently above the wide moat.
Stop for lunch, then continue to Château de Chenonceau—a building whose history is defined by a nearly uninterrupted succession of women. The first chateau was built on this location in the 12th and 13th centuries, although it was burned down in the 14th century. Only the medieval dungeon—Tour des Marque—remains from this construction.
The chateau in its current form was built between 1513 and 1517 by Thomas Bohier and his wife Catherine Briçonnet, who oversaw and directed most of the construction. Since then, there has been a long and dramatic line of women who have owned, loved, repaired, expanded on, and restored the chateau. It's so well-loved, in fact, that it's the second-most visited chateau in France, after Versaille.
After the tour, return to your hotel in Paris.
Day 5: Train from Paris to Avignon & Afternoon in the City
The Palais des Papes (Palace of the Popes) in Avignon
After a last stroll in the city of Lyon, take your train to the beautiful city of Avignon in the heart of Provence.
You'll have the rest of the day to explore this medieval city that housed the Pope in the 14th century. While here you can visit the soaring Palais des Papes—the largest Gothic palace in history and now a UNESCO World Heritage Site. A tour of the palace, which includes the popes' private apartments with their fabulous frescoes, is a must.
You'll also have time to explore the city's pretty squares and the medieval bridge along the Rhone River. Head to Place de l'Horlog, the city's historic heart, to see the City Hall, the 15th-century belfry, the theater, and the still-functioning Belle Époque style carousel. During the 1st century BCE, the plaza was used as Avenio's (then-Avignon) by the Romans as a forum. It's a great place to sit at a cafe and spend the afternoon people watching and enjoying various street performers.
Keep in mind that during July, thousands of visitors flock to Avignon for France's largest art festival.
Day 6: Hilltop Villages & Wine in the Luberon: Full Day Tour
Hilltop village of Gordes
In the morning, embark for the surrounding Luberon Region, an area known for its countryside vineyards, orchards, and postcard-worthy hilltop villages. Travel at a leisurely pace as your guide takes you to the village of l'Isle Sur la Sorgue, famous for its outdoor weekend markets, antique stores, and old wooden waterwheels churning over the Sorgue River, which bisects the town. There are few better spots to enjoy a relaxing lunch than here in town, which is precisely what you'll do.
After eating, head to Gordes. This is arguably the most beautiful of all the hilltop villages in the Luberon. Its fortified castle dominates the skyline of Gordes, and from its winding, cobbled streets, you can look out to wide views over the valley and surrounding hills. From Gordes, it's just a few kilometers to the Abbey of Notre-Dame de Sénanque, a Cistercian abbey founded in the 12th century. Nearby is the village of Roussillon, famous for its colorful ochre. Hike on the Ochre Trail to a former quarry before heading to another hilltop village, Bonnieux.
Drive to Lacoste for panoramic photo stops, then head to Menerbes—your last stop of the day. It's famous thanks to the author Peter Mayle, who chronicled his year in the south of France in his book "A Year in Provence." End the day with wine tasting at a local winery before returning to Avignon for the night.
Day 7: Avignon to Nice, Tour of Aix-en-Provence en Route
Quiet summer day in Aix
On your way to Nice, stop to discover the slow-paced lifestyle and the Provençal charm of Aix-en-Provence.
Spend the morning exploring Aix on a two-hour guided walking tour and uncover the rich heritage, art, and culture that defines the city. Stroll a labyrinth of narrow streets, passing historic churches and squares as your guide points out famous and hidden gems.
Visit the Saint-Sauveur Cathedral, a Romanesque/Gothic church built on the site of an ancient Greek temple to Apollo. Stop and see the Town Hall (known locally as the Hotel de Ville), which dates to the 14th century and sits on an equally old plaza. The tour includes a walk along the Cours Mirabeau, a busy thoroughfare lined with leafy trees and full of markets and cafés—perfect for people watching. Search around to find ruins dating back to the days of the Roman Empire.
At the end of your city tour, continue to Nice.
Day 8: Private Tour of Monaco, Monte Carlo, & Eze
In the morning make your way to Monaco, a 12-mile (20 km) drive from Nice, for a guided tour. Monaco is one of the world's smallest countries and is considered a city-state.
Visit the famous Monte Carlo district with its legendary casino and see Prince Rainier's car collection, then continue to the Rock of Monaco (Rocher de Monaco in French.) This is the location of the town's oldest neighborhood, the medieval Old Town. From here, the views of the sunny coast are unparalleled. Learn about this community's history and anecdotes about the dynasty which has reigned there for decades.
From here continue to the medieval village of Eze, which perches high above the Mediterranean sea. Thanks to its location and history, it's a popular destination with painters and artists. Explore the famous Chapelle Sainte-Croix and the ruins of the ancient castle, which allude to the city's strategic location on the coast. Stroll through the town's peaceful gardens and soak in the sunshine.
At the end of the day, return to Nice.
Day 9: Au revoir, France!
French Riviera by night
After breakfast, take a private car or train transfer to the airport to catch your flight home. A bientôt!
Map of Honeymoon Romance in France: Paris & the French Riviera - 9 Days
Written by Elise Duhem, updated Nov 11, 2019
Plan your trip to France
Chat with a local specialist who can help organize your trip.
France 9-Day Tours & Itineraries
Cycle from Bordeaux to Toulouse - 9 days
See the beautiful Canal de Garonne by bike, via a stunning route through...
Active Family Adventure in Verdon Gorge - 9 Days
This family-friendly itinerary features heart-pumping fun and adventure...
Paris & Provence Road Trip - 9 Days
This scenic itinerary starts with a self-guided road trip through...
Highlights of France in Paris, Bordeaux & the Loire Valle...
Experience three of the major regions of France with this trip through...
Honeymoon Romance in France: Paris & the French Riviera -...
Head to France for nine magical days in the city of love—the perfect...
France Honeymoon
Honeymoon Romance in France: Paris, Lyon, & the French Ri...
If you've got ten days and a heart full of love, head to France for the...
A honeymoon to France is the stuff of dreams, but this real-life...
If you're short on time but don't want to compromise on experience, this...
Honeymoon Romance in France: Paris, Lyon, Avignon, & the ...
Two weeks is the perfect amount of time to get away from it all, which...
How Many Days Should You Spend in Paris?
There's no wrong answer to how much time you should spend in Paris, but...
Food & History in Paris - 9 Days
Explore the City of Lights on this exciting gastronomy and culture tour....
Luxury Getaway to Western France: Paris, Normandy, & Brit...
See Paris from the top of the Eiffel Tower, explore the fishing villages...
Road Trip through Western France: Paris & the Loire Valle...
If you've got six days and want to explore Paris and the Loire Valley,...
Enjoy a quick getaway to Paris and the Normandy coast without...
Best of Provence
How Many Days Should You Spend in Provence?
The French region of Provence is made for explorers—and there's a lot of...
7 Days in Provence - 5 Unique Itinerary Ideas
With a week to spend in Provence, you can tour the region's highlights,...
10 Days in Provence - 4 Unique Itinerary Ideas
With ten days in Provence, you can take your time and enjoy the relaxed...
If you have just five days to spend in Provence, consider taking a road...
Best Time of Year to Visit Provence
The shoulder season months of May and September are the best times to...
Best of the French Riviera
How Many Days Should You Spend in the French Riviera?
With two days to spend in the French Riviera, stick to a couple of key...
Best Time of Year to Visit the French Riviera
The French Riviera is a true pleasure to visit at any time of year....
Cities & Nature in the French Riviera: Nice, Cannes, Mona...
Take it all in on this ultimate fifteen-day luxury trip to the French...
Luxury and culture meet on this eight-day getaway to the sunny French...
Experience the best of the French Riviera, from food and culture in Nice...
France Tours & Itineraries
"Like a Local" Tour in Provence and the French Riviera: 7...
Love getting off the beaten track and traveling like a local? This tour...
Highlights of Provence - 11 Days
Vibrant Marseille, charming Aix-en-Provence, and historic Avignon: pay a...
Paris, Provence & the French Riviera - 10 Days
This itinerary covers a boggling number of must-see places and unique...
The Very Best Walks on Corsica: 7 Days
Amble along windswept coastlines and across dramatic mountain interiors...
Tour du Mont-Blanc Self Guided Trek - 7 days
Circle the highest summit in Western Europe in just six days of trekking...
Make the Most of Your Time in France
How Many Days Should You Spend in France?
For a solid France itinerary that covers two regions plus Paris, a...
5 Days in France - 5 Unique Itinerary Ideas
To make the most of a five-day trip to France, it's best to focus on a...
One week in France is enough time to explore Paris plus the highlights...
10 Days in France - 5 Unique Itinerary Ideas
Planning a ten-day trip to France? If variety is what you're after,...
You can cover some serious ground with two weeks in France, spending...
France Travel Essentials
Best Time of Year to Visit France: Weather, Travel Tips, ...
France offers year-round appeal, whether you're craving sun and sea,...
Best Time of Year to Visit Normandy
Normandy offers beautiful beaches and mild temperatures, a lovely...
How kimkim Trips Work in France
France is known for its world-class wines, picturesque countryside, and...
France Travel Advice
France in January: Travel Tips, Weather, & More
Colder than other months of the year, January is the perfect...
France in February: Travel Tips, Weather, & More
February in France may be right in the middle of the chillier...
France in March: Travel Tips, Weather, & More
One of the lasts months to visit France on a budget, this low-season...
France in April: Travel Tips, Weather, & More
April is a fabulous month to visit France. The weather is delightfully...
France in May: Travel Tips, Weather, & More
No matter where you find yourself in France this month, there's a host...
Ultimate France Itineraries - 5, 7, 10, & 14 Days
Our researchers traveled throughout France. Our experts chipped in with...
France Travel Agents
Kimkim has selected the best France travel agents so you'll have a...
Most Viewed France Content
Tour du Mont Blanc: Self-Guided Trail Run - 6 Days
Follow the classic Tour de Mont Blanc trail on this six-day itinerary,...
Getting Around France
How to Get to Provence
The French region of Provence is famous for its sunny climate, beautiful...
How to Get from Aix-en-Provence to Nice
A distance of approximately 92 miles (148 km) separates Aix-en-Provence...
How to Get from Paris to Marseille
Marseille, France's second-largest city, is 410 miles (660 km) away from...
How to Get from Nice to Verdon Gorge
Nice is approximately 86 miles (138 km) away from the Verdon Gorge, the...
How to Get from Aix en Provence to Saint Tropez
Saint-Tropez is located 63 miles (101 km) southeast of Aix-en-Provence,...
How to Get from Aix en Provence to Marseille
The small, picturesque city of Aix-en-Provence, or just Aix as the...
How to Get from Marseille to Nice
Marseille and Nice lie roughly 100 miles (16) km) apart, on opposite...
How to Get from Paris to Lyon
The distance between France's capital city Paris and the country's...
How to Get from Paris to Aix en Provence
Aix-en-Provence, a small city north of Marseille known as the "city of a...
How to Get from Nice to Cannes
The distance between two destinations on Nice and Cannes on the French...
Mary R.
"Overall this was a wonderful trip, and we were very pleased with our accommodations at Hotel a la Villa des Artistes in the Montparnasse area. That Les Jard..." read more
Traveled to France as a family in February, 2020
Lanier M.
"Our trip was Amazing! Simon was so responsive, both before AND during our trip. I've traveled a lot but never used a travel agent before and what a differenc..." read more
Traveled to France as a couple in February, 2020
Jessica Z.
"Stephen's planning was exactly what we were looking for! Each of the guides/tours he booked for us were excellent - we learned a lot and had a blast the whol..." read more
Traveled to France as a couple in November, 2019
Usha M.
"KimKim did a great job planning for the wants/needs of our group. We used KimKim for transportation, cooking classes, winery tours, and train tickets. I ca..." read more
Traveled to France as a group in September, 2019
"Our trip to Paris was flawless and memorable thanks to Joel's help from Kimkim. From airport pick-up to drop off, we didn't have to worry about anything. Eac..." read more
Traveled to France as a couple in September, 2019
Chandrika J.
"It was a superbly planned and organised trip. Kudos to Lucie who managed the entire planning. As well as Simon from So Provence So Alps! Everything worked li..." read more
Traveled to France solo in August, 2019
Vee M.
"We went for the 7 day self guided tour de Mont Blanc thru kimkim and had an amazing experience. Julien was fantastic communicating frequently and arranging ..." read more
Traveled to France as a family in August, 2019
Lorraine S.
"We trekked from Corte to Evisa over 4 days in July so the weather this year was hot- often in the mid 30's. It was usually a moderate walk with some hard ar..." read more
Traveled to France as a group in July, 2019
Jim Z.
"This is my family's 10 day self-guided TMB trekking. Special appreciation to Julien, the local specialist, who provided consultation and support to my trekki..." read more
Traveled to France as a family in July, 2019
Claudia Dee M.
"This trip was perfection. Our local specialist Simon planned it seamlessly. Each leg of the trip was different and special. The location of the Lyon hotel a..." read more
Create your custom-made trip to France


Street Art Culture In Amsterdam: Exploring Identity and Place | Joy Factory Films | Promotions, Animations, Online Content, Commercials, Video Production and Weddings | Kamloops, B.C.
Once upon a time, I lived in the liberal, bike loving country of The Netherlands. While yes, I spent a lot of time taste testing Dutch craft beer (YUM) and attending free music festivals (SO FUN), I was also hitting the books and working towards my second degree focused on International Marketing. I struggled for a while before I realized that the natural fit for me was studying the ephemeral effects that street art/graffiti can have on an urban landscape. Through photo documentation, interviews, anonymous surveys, attending events and following tour companies around, I suggested that there is a strong, thriving subculture of street art in the capital city of Holland. I'm now a self proclaimed expert (I'm kidding, seriously) on the street art culture's history to present, unique characteristics of this art form in the Amsterdam area, and I can recognize most Dutch artists' work.
Basically, it was an amazing excuse to wander around the canals of Amsterdam and take photos of street art and people watch.
Nowadays, the academic world is actually acknowledging the study of street art, with numerous studies based on larger population epicentres such as London, Paris, Berlin, Bogota, and Seoul. But for Amsterdam, there was not a lot of content written about this glorious city. At first sight, I found that spaces of ordinary life, like an alleyway, could be considered ordinary or banal with an untrained eye; but by looking deeper, the context of street art within space was able to tell a much more complex story. In fact by studying the writings on the walls, it has been said that this is another way of experiencing a city, another way of living. My favourite thing about street art, is that it really is a conversation, usually about hard topics, with many different, creative layers.
So what is "street art"? Well, I basically wrote a book about how street art differs and blurs together with graffiti, urban art, urban interventions, and public art. To sum it up, street art can be anything from a stencil, sticker, a mural or wall painting, or even non-commercial images/posters on a sign post or wall. It can be made with spray paint, brushes, rollers, palettes, stickers, mosaics, and stencils. Street art must be created in an outdoors environment. One of its main components is about having the freedom to paint outside the boundaries – thinking outside of the system, such as a canvas or gallery. There is also entertainment element with it, by providing a space with personal meaning, or connecting to the energy of a city. Street art is usually an illegal form of art found in private and public spaces. Messaging of this art form can have a variety of stories, from political and confrontational, to simply being a creative venture. The artwork created in a moment is unique and can not be replicated in the exact same way in that exact location by the same artist. It could be added to by another artist, lost to weather conditions, or covered up by a municipality worker. Therefore the city becomes a product where the locals and visitors take part in the production of its space; and the city itself becomes a realm which hosts a symbolic value and an ability to generate a sense of common civic belonging. My favourite concept about street art is the idea that it is not simply just one piece on a wall, but a flowing, lively conversation from an almost unseen community.
I like to think of it as a one-time visit to a free, open air museum for everyone and anyone to enjoy.
A'dam is considered to be one of the greatest small cities in the world, as this historical port city is home to over 180 nationalities with different perspectives and backgrounds. Unique architecture of gabled rooftops and tall, thin, brick buildings immediately springs to everyone's mind. It is a city known for a presence of tolerance, diversity, and liberal concepts – but also, a home to resourceful minds incubating creativity. In a way, street art is way for local artists to keep close to their roots while also conquering other popular images of this world class destination, such as Rembrandt, Anne Frank, the Golden Age, and canals.
Street art and graffiti is said to have originated on the streets of the Bronx and Manhattan in the late sixties and early seventies, with famous artists like Keith Haring and Futura 2000. Nothing was left untouched, from sign posts to benches to subway cars, ink was seen everywhere in an underground conversation. From there, a self sustaining culture was created and built upon with leads into a psychical gallery setting. During this same time period and across the Atlantic Ocean, The Netherlands was growing a strong punk rock scene and was idly unaware of what was going on with its American neighbours, until an Amsterdam gallery owner invited American graffiti artists to display artwork in his gallery and these two scenes began mingling together. Quickly, Dutch artists began imitating this graffiti style and growing it into something much more, like the Dutch artist, Shoe, who coined calligraffiti. Quickly, artists began creating their own styles, their own zines, halls of fame, and much more.
Fast forward to the present, and Amsterdam is still charging ahead to be the home of various galleries focused on street art, graffiti, and urban art, a street art themed cafe, the world's biggest street art museum, and many different groups and non-profit organizations, including Amsterdam Street Art.
I had the pleasure of working with the amazing team at Amsterdam Street Art to help them work on a marketing plan and attended the first ever Dutch Street Art Awards in 2016. This was a grassroots celebration focusing specifically on Dutch artists, organizations, galleries, and all that, from across the small, eccentric country. Super cool!
I also found that artists from across the globe are connected, virtually, but also psychically, and often meet up with their crews. This particular cityscape is a hotspot for layovers to a next destination, and the iconic imaging of a liberal holiday in the Red Light District leads to many international artist visits and their works seen across the city centre and outside areas.
Street art is one of those art forms that will endure, as humanity has been writing on walls as far back as recorded data goes. I could really write about this forever, so I'll just close with my researched theory that street art is now a popular, emerging lifeline of every cityscape, despite if it is recognized and encouraged, or heavily discouraged by outside sources.