Ther Connection Machine was able to handle arbitrary n-processors-to-n-processors "sends" in (log2 n) time, but only by interconnecting the processors in a (log2 n)-dimensional hypercube. That's a lot of interconnects...
Also, Connection Machine does not have independent processors that execute arbitrary code and do uncoordinated communications. In traditional CM, everything happens synchronously under control of one global microcode sequencer, so communication can be planned by some offline algorithm that finds optimal paths for any given N to M communication operation.
Also CM "processors" are not CPU's in any meaningful sense. Each CM's processor is essentially multiplexer and few bits of registers. Instruction is presented to the data inputs of multiplexer and processor state goes to the selection inputs with mux output being the next CPU state. In essence it's FPGA turned inside-out.