Replica Exchange Molecular Dynamics (REMD) is a popular method to accelerate conformational sampling of complex molecular systems. The idea is to run several replica of the system at different temperatures that are inter-swapped periodically. These swaps are typically enforced using a discrete-time Markov scheduling based on Metropolis-Hasting acceptance/rejection criterion so as to guarantee that the joint distribution of the replica is the normalized sum of the symmetrized product of the canonical distributions of these replicas at the different temperatures. I will discuss a different implementation of REMD in which the temperature swaps obey a continuous-time Markov jump process implemented via Gillespie’s stochastic simulation algorithm (SSA). This REMD-SSA also samples exactly the aforementioned joint distribution and has the advantage to be rejection free. As a result it permits to accelerate the rate of swapping of the temperature and reach the infinite-swap limit that is known to optimize sampling efficiency. In practice, this infinite-swap limit is implemented by combining REMD-SSA with the heterogeneous multi-scale method (HMM). The method is easy to implement and can be trivially parallelized. I will illustrate its accuracy and efficiency by making the free energy landscape of alanine dipeptide in vacuum and C-terminal β-hairpin of protein G in explicit solvent. I will also discuss a similar generalization of parallel tempering.