Thread-Level Speculation (TLS) overcomes limitations intrinsic with conservativecompile-time auto-parallelizing tools by extracting parallel threads optimistically andonly ensuring absence of data dependence violations at runtime.A significant barrier for adopting TLS (implemented in software) is the overheadsassociated with maintaining speculative state. Previous TLS limit studies observe thaton future multi-core systems it is likely to have more cores idle than those whichtraditional TLS would be able to harness.This thesis describes a novel compact version management data structure optimizedfor space overhead when using a small number of TLS threads. Furthermore, two novelsoftware runtime parallelization systems were developed that utilize this compact datastructure. The first one, MiniTLS, is optimized for fast recovery in the case of misspeculationsby parallelizing the recovery procedure. The second one, Lector, is optimizedfor performance by using lightweight helper threads, along with TLS threads,to establish whether speculation can be withdrawn avoiding that way any speculativeoverheads.Facilitated by the novel compact representation, MiniTLS reduces the space overheadover state-of-the-art software TLS systems between 96% on 2 threads and 40%on 32 threads.MiniTLS and Lector were applied to seven Java benchmarks performing on average7x and 8.2x faster, respectively, against the sequential versions and on average1.7x faster than the current state-of-the-art in software TLS for 32 threads.