Probably do it in a FPGA rather than a CPLD.  Large FIFO's eat up CLB's in
them, but there are a few that have ram blocks (like Xilinx spartan series),
and when Phillips was here touting the CoolRunner, I talked with the
designer of the next generation and she was saying they were going to put
RAM blocks as well.  I'm not sure if that part was ever finished, or what
stage since they were bought out by Xilinx.