Question: I wrote a Java program. For a small input, after warm-up (the first 50 runs), its running time turns to be around 2 milliseconds. 

In this case, could we get any benefit if I use multiple threads version? If not, what are the overhead hidden the benefits of parallel execution?

Answer: 
Most likely the overhead of starting the threads would far outweigh any speedup. On windows you'll even have trouble measuring the execution time reliably for such fast programs.

But of course, you must ask yourself if you truly need any speedup for a program that runs in 2 ms.
Well, 2ms is at least a candidate for splitting up over multiple threads. Continually creating/running/terminating/joining threads is a non-starter - hopeless design. If signaling work to a set of dedicated threads or issuing work to a pool, it all depends on the work done and the data organization.

If there is any blocking, or CPU-intensive, work that an be effectively performed in parallel in those 2ms, then you could give it a go. The key issue with CPU-intensive work is how much data and how it is organized. If the data to be worked on can easily be chopped up into nice, [L1-cache-size or smaller] chunks, you're onto a winner. If not, be prepared for a dissapointment.

You could, of course, try it and see..