A system, method and apparatus for executing instructions in parallel identify a set of traces within a segment of code, such as Java bytecode. Each trace represents a sequence of instructions within the segment of code that are execution structure dependent, such as stack dependent. The system, method and apparatus identify a dependency order between traces in the identified set of traces. The dependency order indicates traces that are dependent upon operation of other traces in the segment of code. The system, method and apparatus can then execute traces within the set of traces in parallel and in an execution order that is based on the identified dependency order, such that at least two traces are executed in parallel and such that if the dependency order indicates that a second trace is dependent upon a first trace, the first trace is executed prior to the second trace. This system provides bytecode level parallelism for Java and other applications that utilize execution structure-based architectures and identifies and efficiently eliminates Java bytecode stack dependency.