This work focuses on the parallel broadcast primitive, where each of the n parties wish to broadcast their \(\ell \) -bit input in parallel. We consider the authenticated model with PKI and digital signatures that is secure against \(t < n/2\) Byzantine faults under a synchronous network. We show a generic reduction from parallel broadcast to a new primitive called graded parallel broadcast and a single instance of validated Byzantine agreement. Using our reduction, we obtain parallel broadcast protocols with \(O(n^2 \ell + \kappa n^3)\) communication ( \(\kappa \) denotes a security parameter) and expected constant rounds. Thus, for inputs of size \(\ell = \varOmega (n)\) bits, our protocols are asymptotically free. Our graded parallel broadcast uses a novel gradecast protocol with multiple grades with asymptotically optimal communication complexity of \(O(n \ell + \kappa n^2)\) for inputs of size \(\ell \) bits. We also present a multi-valued validated Byzantine agreement protocol with asymptotically optimal communication complexity of \(O(n \ell + \kappa n^2)\) for inputs of size \(\ell \) bits in expectation and expected constant rounds. Both of these primitives are of independent interest.