Parallel memory allocation deals with the problems of memory allocations in a multi-threaded application running on a multi-CPU architecture. In contrast to single-CPU architectures one has to consider memory sharing conflicts (locks, cache invalidations and such). For instance two threads running on different CPUs accessing the same cache line again and again may experience a dramatic performance degration because the CPU cannot benefit from its local cache memory since its always invalidated by another CPU.
Before stepping in too deep by writing own routines I'd reccommend using drop-in libraries like hoard (see http://www.hoard.org/) since it is a fairly sophisticated task to test such routines for robustness because of the many race conditions that may occur.
You may check the following document: http://people.cs.umass.edu/~emery/pubs/berger-asplos2000.pdf - It's also about the hoard implementation, but it is also read-worthy since it explains a lot of related issues in depth.