The move to multi-core has increased interest in parallelizing sequential programs. Classical dependency-based techniques, although successful for some classes of programs, often fail due to the one-sided (conservative) approximation of program behavior. Thread-level speculation enables increased parallelism by allowing out-of-order execution: correct dependences are ensured by run-time monitoring and possible rollbacks. Two-sided approximations of program behavior are now acceptable if the rollback ratio is kept small. We describe dynamic analyses, based on representing dependencies as modular congruences, which can be employed on-line or off-line. One, <em>thread partitioning</em> , efficiently enables loop iterations to be allocated to threads (and calculates the maximum effective concurrency); the other, <em>fine-grain memory partitioning</em> , calculates a hash function that reduces space overhead and performance loss due to TLS-metadata-based and cache-based task interference.