As @Adam Siemion said, firstly make sure your PC isn't readily bounded by CPU and you do have a multi-core CPU. Otherwise you cannot be faster anyway.
Secondly, don't create threads dynamically. Use a thread pool with a task queue (See ExecutorService etc in java.util.concurrent). If you are constantly creating threads for large number of small tasks then the thread creation and cleaning up would occupy some considerable amount of time.
Thirdly, I recommend to make sure your threads ends at the same time, Use stuff like CyclicBarrier or CountDownLatch, instead of waiting within the threads on your own.
If the above doesn't resolve your problem, please kindly post some code here. Another guess is you have some shared resource serial dependency, e.g. the painting thread etc.