Parallelization of sequential applications is not a trivial task, but is increasingly important as computing hardware trends to multicore systems. This thesis shows that finding and extracting regions of code for parallelism, as well as software pipelines, can be aided by analysis of dynamic program trace information. However, program traces for just a few seconds of execution are enormous, up to several terabytes in size, uncompressed. Specialized compression can shrink traces to a few gigabytes, but trace analyzers typically stream the decompressed trace through the analysis engine. Thus, the complexity of analysis depends on the decompressed trace size (even though the decompressed trace is never stored to disk). This makes many global or interactive analysis infeasible. This thesis presents a method to compress program traces using binary decision diagrams (BDDs). BDDs intrinsically support operations common to many desirable program analyses and these analyses operate directly on the BDD. Thus, they are often polynomial in the size of the compressed representation. This thesis presents mechanisms to represent a variety of trace data using BDDs and shows that BDDs can store, in 1 GB of RAM, the entire data-dependence graph of traces with over 1 billion instructions. This allows rapid computation of global analyses such as heap-object liveness, dynamic slicing, and DINxRDY time plotting. When combined, these techniques can reveal possible parallel regions of code. This thesis then presents issues germane to the subject of trace BDD creation. Topics included in this discussion include BDD variable orders, as well as BDD creation system RAM. This thesis then presents a tool, ParaMeter, that uses the BDD-trace format to perform program global program trace analysis, such as trace slicing and DINxRDY time plotting. A case study shows the ParaMeter tool in action, which results in a parallelized region of the SPEC INT 2000 benchmark 175.vpr.