  We present an implementation of the coherent dedispersion algorithm capable
of dedispersing high-time-resolution radio observations to many different
dispersion measures (DMs). This approach allows the removal of the dispersive
effects of the interstellar medium and enables searches for pulsed emission
from pulsars and other millisecond-duration transients at low observing
frequencies and/or high DMs where time broadening of the signal due to
dispersive smearing would otherwise severely reduce the sensitivity. The
implementation, called 'cdmt', for Coherent Dispersion Measure Trials, exploits
the parallel processing capability of general-purpose graphics processing units
to accelerate the computations. We describe the coherent dedispersion algorithm
and detail how cdmt implements the algorithm to efficiently compute many
coherent DM trials. We present the concept of a semi-coherent dedispersion
search, where coherently dedispersed trials at coarsely separated DMs are
subsequently incoherently dedispersed at finer steps in DM. The software is
used in an ongoing LOFAR pilot survey to test the feasibility of performing
semi-coherent dedispersion searches for millisecond pulsars at 135MHz. This
pilot survey has led to the discovery of a radio millisecond pulsar -- the
first at these low frequencies. This is the first time that such a broad and
comprehensive search in DM-space has been done using coherent dedispersion, and
we argue that future low-frequency pulsar searches using this approach are both
scientifically compelling and feasible. Finally, we compare the performance of
cdmt with other available alternatives.
