Use GNU Parallel to parallelize your collection:
parallel --slf rhel-nodes --tag --timeout 1000% --onall --retries 3 \
"rpm -q {}; rpm --queryformat '%{installtime:date} %{name}\n' -q {}" \
::: bash bc perl
Put the nodes in ~/.parallel/rhel-nodes.
--tag will prepend the output with the name of the node. --timeout 1000% says that if a command takes 10 times longer than the median to run, it will be killed. --onall will run all commands on all servers. --retries 3 will run a command up to 3 times if it fails. ::: bash bc perl are the packages you want to test for. If you have many packages, use the cat packages | parallel ... syntax instead of the parallel ... ::: packages.
GNU Parallel is a general parallelizer and makes is easy to run jobs in parallel on the same machine or on multiple machines you have ssh access to.
If you have 32 different jobs you want to run on 4 CPUs, a straight forward way to parallelize is to run 8 jobs on each CPU:

GNU Parallel instead spawns a new process when one finishes - keeping the CPUs active and thus saving time:

Installation
If GNU Parallel is not packaged for your distribution, you can do a personal installation, which does not require root access. It can be done in 10 seconds by doing this:
(wget -O - pi.dk/3 || curl pi.dk/3/ || fetch -o - http://pi.dk/3) | bash
For other installation options see http://git.savannah.gnu.org/cgit/parallel.git/tree/README
Learn more
See more examples: http://www.gnu.org/software/parallel/man.html
Watch the intro videos: https://www.youtube.com/playlist?list=PL284C9FF2488BC6D1
Walk through the tutorial: http://www.gnu.org/software/parallel/parallel_tutorial.html
Sign up for the email list to get support: https://lists.gnu.org/mailman/listinfo/parallel