The Parallel Analysis Tools and New Visualization Techniques for Ultra-Large Climate Data Sets (ParVis) project is directly meeting the challenges of analyzing the massive climate model output coming out of BER's climate science program. Climate scientists, computer scientists, and applied mathematicians constitute the ParVis team. ParVis begins with the observation that one of the biggest bottlenecks in visualizing climate output is in the post-processing of climate data, which currently uses decades-old serial programs in a serial workflow. We are first parallelizing this workflow using task parallelism languages such as Swift. We are also developing a Parallel Climate Analysis Library (ParCAL) using technology from DOE's Office of Advanced Scientific Computing Research programs to implement data-parallel versions of many common operations. ParCAL will also have the ability to operate on data from unstructured grid models being developed by BER. ParCAL will be delivered to the climate community through a parallel version of the widely used NCAR Command Language (NCL), a domain-specific language for climate model analysis and visualization. In addition, ParVis is exploring new ways to visualize traditional 2D images in a 3D context, ways to make use of cloud computing paradigms, and how to use compression in climate model output.