I use perl 5.8.0

First. If you are serious about using threads, get a later version of perl. At least 5.8.6. Anything earlier than this has too many bugs to be worth the effort of even attempting to use.

To be clear. Attempting to do anything with threads, even for fun, with 5.8.0 is a pointless exercise in total frustration and doomed to fail.

How can I make the complete subroutine to be executed only after all the threads have completed their processing? If I have to use join, then the threads are consecutively processed rather than parallelly.

You are confused. The following modification to your second() sub will ensure that complete() does not get run until all the threads in @array_of_threads have terminated.

sub second {
        ## creating 5 threads
        for ($i ; $i<5;$i++) {
            $array_of_threads[$i]=threads->new(\&sub1,"$i");
            print "End of thread ".int($i+1)." creation\n";
        }
        $_->join for @array_of_threads; ## Add this 
        &complete();
}
[download]

Where and how were you trying to use join such that you got serialised results?

ps. You don't really use variable names like @array_of_threads do you?

pps. Why use for ($i ; $i<5;$i++) { instead of for( 1 .. 5 ) {?