I have written a Scale2x algorithm, and: or allocate memory in System Memory or GFX mem?

What is faster?

Well, you could benchmark it. A simple FPS counter would work for this case.

Allegro 4 or 5?

It "should" be faster with memory bitmaps because VRAM has much slower access--especially exacerbated on byte-by-byte drawing [which scaling algorithms usually are]. Usually VRAM you just upload your bitmaps/textures, and then use the GPU to "draw" them by copying them onto the screen bitmap. Drawing pixels straight to VRAM is extremely slow.

The fastest way would be to implement a 2x shader and use video bitmaps.

^