Deployment patterns have been proposed as a mechanism to support the provisioning of SOA-based services. Deployment patterns represent the structure and constraints of composite solutions, including non-functional properties, such as performance, availability, and security, without binding to specific resource instances. In previous work [1], we have presented a formal mechanism for capturing such service deployment patterns using models. Our pattern models define abstract connectivity and configuration requirements which are then realized by an existing or planned infrastructure. Realization mapping is used to enforce policies, and is materialized at deployment time. In this paper we extend that work to address the problem of automatic pattern realization over a given infrastructure. We first formalize the problem and present three variations of increasing power and complexity. We then present a variation of a search-based graph isomorphism algorithm with extensions for our pattern model semantics. Next, we show that our worst-case exponential complexity algorithm performs well in practice, over a number of pattern and infrastructure combinations. We speculate that this is because deployment topologies represent heavily labeled and sparse graphs. We present a number of heuristics which we have compared experimentally, and have identified one which performs best across most scenarios. Our algorithm has been incorporated into a large deployment modeling platform, now part of the IBM Rational Software Architect (RSA) tool [2].