I have added a new (small) image size to the theme we develop:
add_image_size('small', 160, 91, TRUE);
How to automatically generate these small images (exactly of the specified size) for every image uploaded in the past?
WordPress doesn't regenerate the newly registered size, only applies it to future uploads.
You'll have to use something like the Regenerate Thumbnails plugin or one of the similar ones available at WordPress.org.