This work presents a hierarchical, parallel, dynamic dependence analysis for inferring runtime dependencies between recursively parallel tasks in the OmpSs programming model. To evaluate the dependence analysis we implement PARTEE, a scalable runtime system that supports implicit synchronization between nested parallel tasks. We evaluate the performance of the resulting runtime system and compare it to Nanos++, the state of the art OmpSs implementation, and Cilk, a high performance task-parallel runtime without implicit task synchronization. We find that i) PARTEE is able to handle more fine grained tasks than Nanos++; ii) PARTEE’s performance is comparable to that of Cilk; iii) in cases where task dependencies are irregular, PARTEE outperforms Cilk by up to 103%.