This dissertation examines the interactions between the on-chip interconnection network and the cache coherence protocol. By exploring the cache-coherent communication behavior of applications, superior performance can be achieved through the co-design of the on-chip interconnect and the cache coherence protocol. The shift toward many-core architectures allows researchers and designers to leverage solutions from the traditional multiprocessor design space. However, these solutions are not always adequate for the differing needs and opportunities presented by many-core architectures. In this dissertation, I seek to challenge some of the conventional wisdom that has been taken from that design space and has emerged in many-core designs and provide alternative solutions to the communication challenges that our industry faces. Communication will be a central component of these large many-core systems; without efficient communication it will be difficult to scale these systems due to both power envelope limits and performance requirements. Two co-designed interconnect and protocol solutions are presented. System performance is sensitive to on-chip communication latency; to address this, we propose hybrid circuit switching. This network design removes circuit setup time by intermingling packet-switched flits with circuit-switched flits. This design is further optimized through a prediction-based coherence protocol that leverages the existence of circuits to optimize pair-wise sharing between cores. The second solution addresses the poor throughput of state-of-the-art on-chip networks in the presence of multicast communication. We present the Virtual Circuit Tree Multicasting router design that removes redundant messages from the network through the construction of multicast trees. Then, we further extend this router architecture to provide network ordering to implement Virtual Tree Coherence. Virtual Tree Coherence is a multicast coherence protocol that leverages both the network ordering and low overhead of our Virtual Circuit Tree Multicasting router to provide low latency cache to cache transfers. By considering on-chip communication from both the perspective of the network and the coherence protocol, superior systems can be designed. The interconnection networks and protocols presented in this dissertation are two such examples.