Update deadlock issue

I'm using SQL server 2005 and running into deadlock issues. I've begun reading up on NO LOCK, but I'm not sure that is the correct way to solve my problem. Any assistance would be greatly appreciated.

I have a batch process that is running every 15 seconds. It generates dynamic UPDATE SQL statements based off a list of foreign keys. To over simplify, imagine the below simple SQL statement:

UPDATE dual
SET val1 = @val1
WHERE fk = @fk
;

Remember this example is over simplified, for each foreign key the SQL statement is actually different, but the table it updates and the values are always the same. I cannot just write a single update statement to deal with all the foreign keys at once.

If I run each statement one at a time everything works fine, but I risk going over my 15 second interval. As a silver bullet, I decided to multi thread the batch application so it would run 25 update statements at once instead of just 1 at a time. After doing this, I begin receiving deadlock errors.

How do I solve this deadlock issue? Three things to remember:

1. The batch is the only application that will ever INSERT, UPDATE, or DELETE records from the table in question


2. Every UPDATE statement uses the foreign key in the WHERE clause, so the batch would never access the same record at once


3. If a record gets bad data, the batch would self correct it in the next run