The paper describes a parallel algorithm for the manipulation of binary decision diagrams on a shared memory multi-processor system. Binary decision diagrams are very efficient representations of logic functions, and are widely used in computer aided design of logic circuits. Logic operations on logic functions such as AND and OR are reduced to operations on binary decision diagrams representing these functions. Operations on binary decision diagrams are time-consuming in some cases, and a fast manipulation method is needed. As with the manipulation, we focus on the construction of a binary decision diagram from a logic formula, and devised a parallel algorithm for the construction. In the construction, there are many logic operations to be processed, and some of them can be processed in parallel. At first, we introduce an extraction method and a parallel-execution method for such parallelizable operations. This is the parallel execution method for an operation sequence (or a set of operations). To extract more parallelism, we introduce a dynamic expansion method of a logic operation. The dynamic expansion is a method to obtain sub-operations from a logic operation using the modified Shannon's expansion. These sub-operations are executed in parallel and the results of these sub-operations are merged to obtain the result of the original operation. Our parallel algorithm, which is based on the construction of shared binary decision diagrams with the negative edge and the operation cache, is implemented in C on a shared memory multi-processor system Sequent S-81 (CPU 80386 (16 MHz)28, 86.75MB), and applied to multiplier examples and ISCAS benchmarks. The speed-up ratio becomes 14 for multipliers, and becomes 11 for c1908 in ISCAS benchmarks.