I totally agree with Justin on the parallelism business. After turning it off, the performance more than doubled in my system.
In addition, parallelism can also lead to a phenomena known as CPU starvation. It works like this, let’s say you have different 20 queries in the queue and an 8 CPU box. Typically many of them would execute simultaneously since they all hit different tables. However, with parallelism, SQL Server breaks up the first query into 7 pieces and sends them off to 7 different CPUs. Now most CPUs are busy and the ones that completed processing are waiting for the results from other CPUs to trickle in.
Meanwhile, the queries in the queue, are sitting around waiting. Then, if the queue wait timeout is hit, SQL Server dumps the queries into tempdb, to be retrieved milliseconds later, when CPUs are available. So all of a sudden, your system is going to hell because of all the writes to tempdb.
As far as the deadlocks are concerned, I’d throw several traceflags on the system - they will tell you exactly why (and what keys, indexes, etc… are involved) your deadlocks are happening.
Try this for starters,
http://support.microsoft.com/kb/832524
then if you need some more help, contact me via the blog.
Regards
Robert